백준 2166번 다각형의 면적

링크텍스트

• 알고리즘
  외적(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;
}