Kattis - Polygon Area

We can use the shoelace theorem to find the area of the polygon.

Recall that the sign of the resulting area determines the direction in which the vertices are given. For our implementation, the vertices are given clockwise if the area is negative, and counterclockwise otherwise.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
 Code Snippet: C++ Short Template (Click to expand)

// 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; }