2284. Is This Polygon Simple
n points are given in order. They describe the closed path
v0 -> v1 -> ... -> v(n-1) -> v0. Decide whether that path is a SIMPLE polygon
and print YES or NO.
Simple means all four of these hold:
1. no vertex is repeated
2. every edge has positive length
3. two consecutive edges meet only at the vertex between them
4. two edges that are not consecutive have no point in common at all
(0,0) (4,0) (4,4) (0,4) -> YES a square
(0,0) (4,4) (4,0) (0,4) -> NO the bow tie, two edges cross
(0,0) (2,0) (4,0) -> NO flat: the closing edge covers the others
Conditions 1 and 2 are the same condition for a closed path, since a repeated consecutive vertex is a zero-length edge. Both are stated because a repeat that is NOT consecutive is a pinch point, which conditions 3 and 4 would also catch but which is much clearer to reject directly.
## What most people try first
Testing every pair of non-consecutive edges with a strict crossing test and stopping there. That misses three whole families, and each one has a declared test here.
It misses collinear overlap. Edges (0,0)-(4,0) and (2,0)-(6,0) share a
stretch, and a straddle test built on strictly opposite signs answers NO to
them, because every determinant involved is zero.
It misses the consecutive pair. Two edges that share a vertex are supposed to
share it, so they get skipped, and then a path that doubles straight back on
itself, (0,0) -> (4,0) -> (2,0), passes: those two edges are consecutive and
overlap along two units.
And it misses the repeated vertex. A path that returns to an earlier point and leaves again in a new direction has two edges meeting at a point that is an endpoint of both, which a crossing test treats as fine.
## The check, pair by pair
Take every unordered pair of edges i < j.
consecutive <-> j == i + 1, or i == 0 and j == n - 1
The wrap-around pair (0, n-1) is the one that gets forgotten, and the input
(0,0) (2,0) (4,0) exists to catch exactly that: edges 0 and 1 are fine
with each other, and it is the closing edge that lies on top of them.
For a consecutive pair, the only legal shared point is the vertex between them, so check that neither FAR endpoint lies on the other edge. For a pair that is not consecutive, use the full exact predicate and reject on any shared point at all, which means the straddle test plus the four on-segment tests, so that touching and collinear overlap are both caught.
With n up to 1000 that is about 500000 pairs and a few multiplications each,
which is the intended cost.
## Width
Coordinates satisfy |x|, |y| <= 1000000, so each coordinate difference is at most 2 * 10^6, each product of two differences at most 4 * 10^12, and a cross product at most 8 * 10^12 in magnitude. A signed 32-bit integer stops at 2147483647, so a 32-bit cross product wraps and reports the wrong SIGN, which is a wrong answer and not merely a wrong number. The value is below 2^53 = 9007199254740992, so a JavaScript Number holds it exactly and no BigInt is needed; the bitwise operators must not appear, because they coerce to 32 bits.
Constraints - `3 <= n <= 1000` - `-1000000 <= x, y <= 1000000` - the vertices are given in path order and need not be distinct
Input
The first line contains an integer n.
Each of the next n lines contains two integers x y, one vertex, in path order.
Output
Print YES if the closed path is a simple polygon and NO otherwise, in upper case, alone on a line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.