2287. The Area Left After the Holes

An outer simple polygon has h holes punched in it, each itself a simple polygon lying strictly inside the outer one, and no two holes touching each other. Print TWICE the area of the material that is left.

outer (0,0) (10,0) (10,10) (0,10) area 100 hole (2,2) (4,2) (4,4) (2,4) area 4 -> 192 which is 2 * (100 - 4)

## What most people try first

Adding the shoelace sums together and hoping the signs sort themselves out. There is a real convention in which that works: list the outer boundary anticlockwise, list each hole CLOCKWISE, and the signed sums add up to the net area directly. It is the convention that graphics formats and polygon libraries use, and it is worth knowing.

It is also why this problem does not promise it. The input gives each polygon in an arbitrary direction, so a bare sum of signed areas may come out as the outer area plus a hole, or minus it, depending on how the data happened to be written. A solution that relies on the convention is right on half the inputs, which is the worst kind of wrong.

## What to do instead

Take the shoelace sum of each polygon, take its ABSOLUTE value, and then subtract: outer minus the sum of the holes. The absolute value throws away the winding, which is exactly the information that cannot be trusted here, and the containment promise in the constraints supplies what is needed in its place. Because every hole is strictly inside the outer polygon and no two holes meet, the material left is the outer region with each hole region removed once, so areas subtract with no overlap correction.

## The subtraction is the whole problem

Both the sum and the difference stay integers, so the answer is exact. Note that the result is 2 * (outer area - total hole area), which is the difference of two DOUBLED areas: there is no point at which a halving is needed, and inserting one would be the only inexact step in the program.

The answer is positive, because a hole strictly inside the outer polygon has strictly smaller area. With h = 0 the answer is simply twice the outer area.

## 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.

The cap applies to the TOTAL number of vertices across the outer polygon and all the holes, so the running sum obeys the same bound whichever way the vertices are distributed.

Constraints - `0 <= h <= 100` - `3 <= m <= 1000` for each polygon - the total number of vertices over all polygons is at most 1000 - `-1000000 <= x, y <= 1000000` - every polygon is simple, and its vertices are given in order around its boundary in either direction - every hole lies strictly inside the outer polygon, and no two holes share a point