문제
https://www.acmicpc.net/problem/2166
문제풀이
ccw를 이용하여 다각형의 면적을 구하는 문제이다.
ccw자체가 외적을 구하는 것이기 때문에 ccw의 결과값은
세 점으로 이루어진 평행사변형의 넓이가 된다.
평행사변형을 2로 나눈다면 삼각형이 되고
모든 n각형 도형은 삼각형으로 나눌 수 있다.
예를들어 설명해보면
반복문을 돌면서
a-b-c의 ccw + b-c-d의 ccw … a-e-f의 ccw
계산을 해주면 전체 도형의 넓이를 구할 수 있다.
다만 ccw에 넣는 순서에 따라 결과값이
음수로 나올수도 있기 때문에 최종 결과값에 절대값을 붙여줘야 한다.
이제 이런 경우를 생각해보자
이 경우는 어떻게 계산을 해야할까
신기하게도 그냥 첫번째 계산과 마찬가지로 계산해주면 된다.
왜 그런지 생각해보면
a-b-c의 ccw를 구하고 거기다 a-c-d의 ccw를 더하게되면
a-b-c의 ccw의 값과 a-c-d의 ccw의 값은 서로 다른 부호를 갖게 된다.
ccw의 방향이 다르기 때문에
하나가 양수라면 다른 하나는 음수가 나오는 것이다.
그래서 전체 도형에서 오목하게 들어간 부분을 빼주는 것이 된다.
결국 이 문제는 한점을 기준으로 반복문을 돌며 ccw들을 더해주면 된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
typedef pair<double, double>P;
double ccw(double x1, double x2, double x3, double y1, double y2, double y3) {
double res = x1 * y2 + x2 * y3 + x3 * y1;
res += (-y1 * x2 - y2 * x3 - y3 * x1);
return res / 2;
}
int main() {
int n; cin >> n;
vector<P>arr(n);
for (int i = 0; i < n; i++)
scanf("%lf%lf", &arr[i].first, &arr[i].second);
double res = 0;
for (int i = 1; i < n; i++)
res += ccw(arr[0].first, arr[i - 1].first, arr[i].first, arr[0].second, arr[i - 1].second, arr[i].second);
printf("%.1lf", abs(res));
return 0;
}