2290. Both Halves of a Diagonal Cut

A simple polygon is given by its n vertices in order, numbered 0 to n-1. Each query names two vertices i and j that are not neighbours. Cutting along that diagonal leaves two closed vertex lists:

first half: v_i, v_(i+1), ..., v_j second half: v_j, v_(j+1), ..., v_(n-1), v_0, ..., v_i

Print TWICE the SIGNED area of each, in that order.

square (0,0) (4,0) (4,4) (0,4), query 0 2 -> 16 16 same square listed clockwise, query 0 2 -> -16 -16

## Signed, and why that makes the problem well posed

The sign is kept rather than thrown away, and it is what makes the answer meaningful for a concave polygon. The two values ALWAYS add up to twice the signed area of the whole polygon, for every polygon and every pair i < j, whether or not the diagonal happens to lie inside.

The reason is short. The shoelace sum is a sum of one term per edge. The first half uses the edges i -> i+1 up to j-1 -> j and then the closing edge j -> i. The second half uses the remaining edges and then the closing edge i -> j. The two closing terms are

(x_j * y_i - x_i * y_j) and (x_i * y_j - x_j * y_i)

which are negatives of each other, so they cancel, and what is left is exactly the full shoelace sum.

Taking absolute values would break that. For a diagonal that leaves the polygon the two regions overlap, their signed areas have the sum above but their magnitudes do not add up to anything in particular. Keeping the sign makes the question answerable for every input instead of only for the convex ones, which is why this problem asks for it.

## What most people try first

Rebuilding each half as a list and running the shoelace sum over it. That is correct, and at q queries of a polygon with n vertices it costs q * n. With q up to 100000 and n up to 1000 that is 10^8 term evaluations, which is the wrong shape for a problem whose answer is a RANGE SUM.

## Prefix sums over the edge terms

Let t_k = x_k * y_(k+1) - x_(k+1) * y_k for k from 0 to n-1, with the index wrapping, and let S_m = t_0 + ... + t_(m-1). Then

first half = (S_j - S_i) + (x_j * y_i - x_i * y_j) second half = full - first half

where full = S_n. Each query is then two multiplications and a subtraction, and the preparation is one pass. The second line is not a shortcut, it is the cancellation argument above, used as an identity.

## 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 prefix values are partial shoelace sums and obey the same 2 * 10^15 bound, so the prefix ARRAY needs the wide type and not only the final answer.

Constraints - `4 <= n <= 1000` - `1 <= q <= 100000` - `-1000000 <= x, y <= 1000000` - the polygon is simple and its vertices are given in order around the boundary in either direction - `0 <= i < j <= n-1`, with `j >= i + 2`, and not both `i = 0` and `j = n-1`, so the two named vertices are never neighbours