백준 2166 - 다각형의 면적 (신발끈 공식)

https://www.acmicpc.net/problem/2166

2166번: 다각형의 면적

볼록다각형에서 반드시 적용할 수 있는 '신발끈 공식'을 이용해 푸는 문제이다.

 

신발끈 공식이란 다음과 같다.

N개의 좌표 (x1, y1) ~ (xn, yn) 위 점으로 구성된 N각형의 넓이를 S라고 하자.

S = 1/2 * |(x1 * y2 + x2 * y3 + ... + x(n-1) * yn + xn * y1) - (x2 * y1 + x3 * y2 + ... + xn * y(n-1) + x1 * yn)|

 

신발끈 공식이라는 이름을 갖게 된 이유는 위 공식을 시각적으로 표현해보면 알 수 있다.

직접 그림

.... 식에서 곱해지는 값들을 선으로 연결하면 위 그림처럼 신발끈의 비주얼이 나타나기 때문이다. 빨간 선으로 곱한 값들의 합과 파란 선으로 곱한 값들의 합의 차를 구해 거기에 1/2를 곱하면 된다. (중요) 이때, (x1, y1)부터 (xn, yn)까지의 좌표는 시계방향, 또는 반시계방향으로 순서대로 놓여져있어야 한다. 순서가 섞여있으면 잘못된 결과를 얻게 된다.

 

다행히도 이 문제에서는 '다각형을 이루는 순서대로' 좌표가 주어졌기 때문에 무조건 입력순서가 시계 또는 반시계방향임이 보장된다. 만약 랜덤으로 주어졌다면 어떡해야 할지 참 막막하다 좌표를 정렬하기 위해 별도의 처리를 해줘야 할 것이다. 그 처리는 그때 가서 생각해보도록 하자.

 

신발끈 공식을 코드로 옮기는 건 어렵지 않다. Xi * Yj의 최댓값은 100억이고 이 값이 최대 1만개까지 더해질 수 있으므로 오버플로우만 방지하면 된다.

 

추가로 단순화를 위한 간단한 팁을 들면서 풀이를 마친다.

1) 모듈러 연산을 사용해 반복문 안에서 xn * y1, x1 * yn을 처리

long long top = 0, bot = 0; //top : 빨간 선 부분, bot : 파란 선 부분
for (int i = 0; i < N ; i++) {
    top += X[i] * Y[(i + 1) % N];
    bot += Y[i] * X[(i + 1) % N];
}

2) 실수형 결과값을 생성하기 위해 |top - bot|에 1/2를 곱할 때, 1/2를 앞에 두면 명시적 형변환 (double) 생략 가능

//0.5가 앞에 있을 때
double result = 0.5 * abs(top - bot);

//0.5가 뒤에 있을 때
double result = (double)abs(top - bot) * 0.5;