Polygon Area — Shoelace Formula
The shoelace formula computes a polygon’s area by summing local edge determinants. For integer coordinates its doubled area is an exact integer, so even a half-integer area can be printed without floating-point rounding. The program reports both the signed doubled area and the ordinary nonnegative area. This separation makes vertex-order effects visible and supports later lattice-point counting.
Prerequisites: Polygon Representation and Properties; signed cross products.
Build the idea
Derive from oriented triangles
For an edge A→B, cross(A,B)/2 is the signed area of triangle OAB with O at the origin. Sum these edge triangles around a simple polygon. Contributions outside the polygon cancel with opposite signs, while points inside contribute once according to orientation. The origin need not lie inside: the signed cancellation argument still applies.
Write the cyclic sum
Expand each cross as xi·y(i+1)−yi·x(i+1), including the final-to-first edge. The two diagonal-looking product sums explain the name shoelace. Keep the signed total until the end. Taking absolute values term by term destroys the cancellation and can overcount drastically when the origin lies outside the polygon.
Preserve exact doubled area
Integer products and their sum give an integer A2. The actual area is |A2|/2. Print |A2|/2 as integer division and append .0 or .5 according to its parity. This avoids losing the final half unit to binary floating representation or truncating it accidentally. Widen operands before products when using smaller stored types.
Trace a half-unit answer
For the triangle (0,0),(3,0),(0,3), the first and final cross terms are zero and the middle term is 9. Signed doubled area is 9, so area is 4.5. Reversing the vertex order changes 9 to −9, but the unsigned area remains 4.5. Translation also leaves the final area unchanged because added edge terms telescope.
State what the formula measures
The implementation requires a simple polygon without holes, in boundary order. A self-intersecting chain produces an algebraic signed area with cancellations, not necessarily the visible union area. A polygon with holes needs separately oriented boundaries or an explicit outer-minus-holes calculation. We do not silently apply a simple-polygon formula to a different object.
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
#include<iostream>
#include<vector>
#include<cstdlib>
struct Point{
long long x,y;
};
int main(){
int n;
std::cin>>n;
std::vector<Point>p(n);
for(auto&a:p){
std::cin>>a.x>>a.y;
}
long long twice=0;
// Sum signed edge determinants first; absolute values per edge would be wrong.
for(int i=0;i<n;++i){
Point a=p[i],b=p[(i+1)%n];
twice+=a.x*b.y-a.y*b.x;
}
std::cout<<twice<<'\n';
long long absolute=std::llabs(twice);
std::cout<<absolute/2<<(absolute%2?".5":".0")<<'\n'; // No floating conversion needed.
}
Complexity analysis
O(n) time for one edge scan and O(n) vertex storage. Under the bounds, the absolute sum of determinant magnitudes is at most 2·10^17, safely in long long. Larger n or coordinate ranges need a new bound and possibly wider arithmetic.
Example input and output
Read n (3..100000) and a simple polygon with integer coordinates within ±10^6, no repeated closing vertex. Print signed doubled area, then nonnegative area with .0 or .5.
Input
3 0 0 3 0 0 3
Output
9 4.5
The only nonzero edge determinant is 3·3=9; dividing doubled area by two yields 4.5.
Practical applications
Use for region areas, hull area, polygon orientation and Pick’s theorem. Rectangle union area is a different problem because overlaps must be counted once. Triangulation is useful when the task needs explicit triangles rather than just a scalar area.
Check your understanding
Why keep the doubled area until output?
Put it into practice
Translate the sample by (100,−50) and reverse its order.
Show a hint
Translation preserves both area values; reversal negates only the signed one.