2291. The Area of a Closed Walk
A walk starts at the origin and takes n steps, each given as a displacement
(dx, dy). If the walk returns to the origin, print TWICE the absolute value of
the signed area it encloses. If it does not return, print NOT CLOSED.
(4,0) (0,4) (-4,0) (0,-4) -> 32 a 4 by 4 square
(4,0) (-4,3) (0,-3) -> 12 a triangle
(4,0) (0,4) (-4,0) (0,-3) -> NOT CLOSED it ends at (0,1)
## What most people try first
Trying to measure the enclosed region directly, which needs the path to be turned into a polygon first and is a much harder problem than it looks. The useful observation is that the shoelace sum does not need the region at all: it only needs the sequence of positions, and the positions are the running totals of the displacements.
The second instinct is to test closure by looking at the final position after
the last step, which is right, and then to build the position list including
that final point, which is wrong. The position list has n entries, not n + 1:
the walk's last position IS the starting point again, and listing it twice adds
a zero-length edge and, worse, makes the shoelace wrap close the polygon through
the wrong vertex.
## The closure test comes first, and costs nothing
The walk is closed exactly when the displacements sum to (0, 0), component by
component. That is two integer sums and it has to be checked BEFORE any area is
computed, because the shoelace formula applied to a path that does not close
returns a number, and the number means nothing.
## Then the shoelace sum over the running positions
p_0 = (0,0)
p_k = p_(k-1) + step_(k-1) for k = 1 .. n-1
2A = sum over k of ( x_k * y_(k+1) - x_(k+1) * y_k ), index wrapping
Because the walk closes, the wrap from p_(n-1) back to p_0 is exactly the
last step, so the closing edge is the one the input supplies and nothing is
invented.
## What the answer means when the walk crosses itself
The displacements are not promised to describe a simple path, and a self-crossing
closed walk does not enclose one region. The statement therefore asks for twice
the absolute value of the SIGNED area, the number the shoelace sum produces,
which is what the formula computes whether or not the walk is simple. For a
figure of eight the two loops wind in opposite directions and cancel, so the
answer can be 0 even though the walk visits plenty of ground. That is the
defined answer here, not a bug, and the figure-of-eight case is a declared test.
A step may be (0, 0). It leaves the position unchanged, contributes a zero
term, and needs no special handling.
## Width
Each displacement satisfies |dx|, |dy| <= 1000 with n at most 1000, so every
position stays within |x|, |y| <= 1000000 and the bound on the shoelace sum is
the usual one: a single term at most 2 * 10^12, the running sum at most
2 * 10^15, which is below 2^53 = 9007199254740992 so a JavaScript Number
is exact. A signed 32-bit accumulator stops at 2147483647 and is wrong well
before the limit.
Constraints - `1 <= n <= 1000` - `-1000 <= dx, dy <= 1000` - a step may be `0 0`, and the walk need not be a simple path
Input
The first line contains an integer n.
Each of the next n lines contains two integers dx dy, one step of the walk, in order.
Output
Print NOT CLOSED in upper case if the steps do not sum to zero in both components. Otherwise print one integer, twice the absolute value of the signed area of the closed walk. Either way print nothing else on the line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.