알고리즘
외적(cross product)을 이용하여 풀 수 있는 문제다. 점이 순서대로 주어지므로, 연속되는 두 점에 대한 외적값의 절반을 모두 더하면 된다.
시간복잡도
점의 개수를 n이라 할 때, 시간복잡도는 O(n)이다.
응용
외적은 이외에도 CCW 등에 사용된다. CCW(counter clockwise)는 어떤 점이 벡터에 대해 반시계 방향에 있다는 것을 의미한다. 즉, 벡터와 벡터의 시작점-목표점 간의 외적값이 양수면 counter clockwise, 음수면 clockwise이다. 한 점이 convex polygon(볼록 다각형)의 내부/외부에 있는지 판별할 때에도 사용할 수 있다. 다각형의 모든 선분에 대해 점이 counter clockwise 방향에 있는지 확인하면 된다.
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#define MAX_POINTS 10000
#define MAX_COORD 10000
using namespace std;
typedef pair<long double, double> pdd;
int n;
pdd points[MAX_POINTS];
inline double CCW(pdd point1, pdd point2) {
return (point2.first * point1.second - point2.second * point1.first) / 2;
}
double getPolygonArea() {
double retval = 0;
for (int i = 0; i < n - 1; i++) {
retval += CCW(points[i], points[i + 1]);
}
retval += CCW(points[n - 1], points[0]);
return retval;
}
int main(void) {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> points[i].first >> points[i].second;
}
printf("%.1lf \n", round(abs(getPolygonArea()) * 10) / 10);
return 0;
}