2302. Twice the Area of the Hull
Given n points with integer coordinates, print TWICE the area of their convex
hull.
Twice, not the area itself, so that the answer is always an integer and no division or rounding enters the problem. The true area of a polygon with integer corners is either an integer or an integer plus one half, so doubling it is exactly the right question to ask.
(0,0) (4,0) (4,4) (0,4) -> 32 a 4 by 4 square has area 16
(0,0) (4,0) (0,3) -> 12 a triangle of area 6
(0,0) (1,0) (2,0) -> 0 a flat hull has no area
(3,3) (3,3) (3,3) -> 0 one point has no area
## What most people try first
Shoelace over the points in input order. That computes twice the signed area of the polygon you get by joining the points in the order they were typed, which is a self-crossing scribble, not the hull. The area of the hull is a property of the SET, so the hull has to be built first.
The second instinct is to divide by two and print a real number, which turns an exact question into an argument about how many decimal places to accept.
## The method
Build the hull with Andrew's monotone chain, dropping collinear boundary points since they do not change the area. Then triangulate it as a fan from its FIRST corner and sum the doubled triangle areas:
h = hull(points) anticlockwise, k corners
answer = sum over i = 1 .. k-2 of cross(h[0], h[i], h[i+1])
An empty sum is zero, which is what a one-point or all-collinear hull should give, so the two degenerate cases need no special code.
## Why it is correct
cross(A, B, C) is twice the signed area of triangle ABC, positive when ABC
turns anticlockwise. The hull is convex and listed anticlockwise, so every fan
triangle h[0] h[i] h[i+1] turns anticlockwise and every term is positive. The
fan triangles tile the polygon and overlap only on the diagonals, which have no
area, so the sum is exactly twice the polygon's area.
## Why the fan and not the raw shoelace
The ordinary shoelace sum adds x_i * y_{i+1} - x_{i+1} * y_i over absolute
coordinates. Each of those terms reaches 10^12 and they do not cancel until the
very end, so with 200000 corners the running total can reach about 4 * 10^17.
That still fits in a signed 64-bit integer, but it does NOT fit in a double, so
in JavaScript the raw shoelace silently loses the low bits. The fan from h[0]
differs: every term is positive and every partial sum is itself twice the area of
part of the hull, so no partial sum exceeds the final answer.
## Width
The hull lies in a 2 * 10^6 by 2 * 10^6 box, so twice its area is at most
8 * 10^12. That needs a 64-bit integer, since a signed 32-bit one stops at
2147483647, and it is below 2^53 = 9007199254740992, so a JavaScript Number
holds every partial sum of the fan exactly.
## Cost
O(n log n) time, dominated by the sort, and O(n) memory.
Constraints - `1 <= n <= 200000` - `-1000000 <= x, y <= 1000000` - points need not be distinct, and a degenerate hull has doubled area `0` - the answer is at most `8 * 10^12`, which a signed 32-bit integer cannot hold
Input
The first line contains an integer n.
Each of the next n lines contains two integers x y, one point.
Output
Print one integer, twice the area of the convex hull of the given points, alone on a line. Print 0 when the hull is a single point or a segment.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.