Skip to Content
CTRL K

Polygon Area

Podemos usar el teorema del cordón (shoelace) para hallar el área del polígono.

Recordemos que el signo del área resultante determina la dirección en la que se dan los vértices. En nuestra implementación, los vértices se dan en sentido horario si el área es negativa, y en sentido antihorario en caso contrario.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

// CodeSnip{CPP Short Template}
 
// From KACTL: https://github.com/kth-competitive-programming/kactl
 
template <class T> struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
	P operator-(P p) const { return P(x - p.x, y - p.y); }
	T cross(P p) const { return x * p.y - y * p.x; }
	T cross(P a, P b) const { return (a - *this).cross(b - *this); }
};
 
template <class T> T polygonArea2(vector<Point<T>> &v) {
	T a = v.back().cross(v[0]);
	for (int i = 0; i < sz(v) - 1; i++) a += v[i].cross(v[i + 1]);
	return a;
}
 
typedef Point<long double> P;
 
void solve(int n) {
	vector<P> pts(n);
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		pts[i] = P(a, b);
	}
 
	// implementation has 2x polygon area
	long double area = polygonArea2(pts) / 2;
	(area < 0) ? cout << "CW " : cout << "CCW ";
 
	cout << fixed << setprecision(1) << abs(area) << "\n";
}
 
int main() {
	setIO();
	for (;;) {
		int n;
		cin >> n;
		if (!n) break;
		solve(n);
	}
}
Fundamentos