[BOJ] 2166. 다각형의 면적 (JavaScript)

gitgitWi's TIL·2021년 2월 10일
1

BOJ 도장깨기

목록 보기
4/4

2166. 다각형의 면적

문제 요약

N각형의 꼭지점 좌표 N개가 주어질 때, 이 다각형의 면적

회고

그냥 수학 문제?

단 한 줄 밖에 없는 문제 내용을 읽고 나서,
몇 분 동안은 '이걸 어떻게 풀어?'라는 생각밖에 안들었다

세 점의 좌표가 있을 때 삼각형 넓이 구하는 공식이 있지 않을까 검색해보니,
신발끈 공식이라는 생각보다 간단한 공식을 발견할 수 있었고,
기하 알고리즘의 하나로 CCW라는 것을 알게 되었다

너무 오랜만에 본 벡터라 처음에 접근하기 힘들었지만,
관련 지식이 있다면 너무 쉬운 문제일수도

신발끈 공식을 적용한 풀이

  • 출발점과 다른 두 점으로 만들어지는 삼각형의 넒이를 벡터 외적을 활용한 신발끈 공식으로 구한 후
  • 이 삼각형들의 총합을 구하면 다각형의 총 넓이가 된다
  • 이때 별모양처럼 오목한 다각형은 합이 음수가 나오므로 반드시 절대값으로 변환해야 함
  • 오목 다각형인 경우 음수가 나오는 문제 때문에 더해지는 순서도 중요한데, 이 문제에서는 출발점부터 마지막 점까지 차례대로 좌표가 주어지기 때문에 차례대로 하나씩 더하면 됨
  • 참고: 위키백과 > 신발끈_공식

CCW; Counter Clockwise

/**
 * @param {string[]} input stdin, 3<= N <=10,000
 * @returns 다각형의 면적, 소수점 둘째 자리에서 반올림
 */
const solution = (input) => {
  const [N, ...dots] = input;
  const points = dots.map((d) => d.split(" ").map(Number));
  const [startX, startY] = points[0];

  const getTri = (a, b) => {
    const [ax, ay] = a;
    const [bx, by] = b;
    return (ax - startX) * (by - startY) - (ay - startY) * (bx - startX);
  };

  let ans = 0;
  for (let i = 2; i < N; i++) {
    ans += getTri(points[i], points[i - 1]);
  }

  return (Math.abs(ans) * 0.5).toFixed(1);
};

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
console.log(solution(input));
profile
가볍게 TIL 남기는 velog, 꾸준히 성장하는 개발자

0개의 댓글