2286. Twice the Area of a Polygon
A simple polygon is given by its n vertices in order around the boundary.
Print TWICE its area.
(0,0) (4,0) (4,4) (0,4) -> 32 a 4 by 4 square, area 16
(0,0) (4,0) (0,3) -> 12 a right triangle, area 6
(0,0) (4,0) (4,4) (2,2) (0,4) -> 24 a square with a notch cut out
## Why twice, and not the area
The area of a lattice polygon is a multiple of one half and nothing smaller, so it is a whole number or a whole number plus a half. Doubling it makes the answer an integer in every case, and an integer answer can be compared exactly. Halving it would introduce the one and only division in this problem and turn an exact question into a question about rounding, for no gain. So the problem asks for the doubled area throughout, as the rest of this topic does.
## What most people try first
Splitting the polygon into triangles by eye and adding up. It works for a convex polygon and it collapses for a concave one: a diagonal drawn from the wrong vertex leaves the polygon, and some triangles then have to be subtracted rather than added, with no obvious rule for which.
The shoelace formula does the bookkeeping instead, and the sign does the subtraction automatically.
## The shoelace sum
2A = sum over i of ( x_i * y_(i+1) - x_(i+1) * y_i )
with the index wrapping so that the last vertex pairs with the first. Each term is twice the signed area of the triangle formed by the origin and the edge, and the parts of those triangles that stick out beyond the polygon are covered twice with opposite signs, so they cancel. That is why a concave polygon needs no special treatment: a fan from vertex zero works for the same reason.
Do not forget the closing term. Dropping the wrap is the single most common bug here, and it does not produce a wild answer, just a slightly wrong one, which is much harder to notice.
## Winding, and why the answer is an absolute value
The sum is POSITIVE when the vertices are listed anticlockwise and NEGATIVE when
they are listed clockwise, with the same magnitude either way. This problem does
not say which order the input uses, so take the absolute value at the end. A
degenerate polygon whose vertices are all on one line has a sum of exactly zero,
and the answer is then 0.
## Width
Coordinates satisfy |x|, |y| <= 1000000 and the polygon has at most 1000 vertices. One shoelace term x_i * y_(i+1) - x_(i+1) * y_i is therefore at most 2 * 10^12 in magnitude, and the running sum at most 2 * 10^15. A signed 32-bit integer stops at 2147483647, so a 32-bit accumulator is wrong from a square of side 47000 upward. 2 * 10^15 is below 2^53 = 9007199254740992, so a JavaScript Number holds every partial sum exactly and no BigInt is needed; the bitwise operators must not appear, because they coerce to 32 bits. The vertex cap of 1000 is what makes that claim true, and it is the reason the cap is there.
Constraints - `3 <= n <= 1000` - `-1000000 <= x, y <= 1000000` - the polygon is simple, that is no two edges cross, and the vertices are given in order around the boundary in either direction - the vertices may be collinear, in which case the area is 0
Input
The first line contains an integer n.
Each of the next n lines contains two integers x y, one vertex, in order around the boundary.
Output
Print one integer, twice the area of the polygon, alone on a line. The value is never negative.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.