2276. Does the Path Always Turn the Same Way

A path visits n points in the given order. Print YES if every turn along it goes the same way, and NO if some turn goes left while another goes right. Points where the path goes straight on count as neither and are ignored.

(0,0) (1,0) (1,1) (0,1) -> YES every turn is a left turn (0,0) (1,0) (1,1) (2,0) -> NO left then right (0,0) (1,0) (2,0) -> YES no turn at all

## What most people try first

Comparing every pair of turns, which is O(n^2) and unnecessary: "all the non-zero signs are equal" can be decided in one pass by remembering the first non-zero sign and checking the rest against it.

The subtler mistake is treating a straight stretch as a turn. If the sign is recorded as 0 and then compared against a later +1, the path is wrongly reported as turning both ways. Three collinear consecutive points are not a turn in either direction, and a path may have many of them and still be convex, which is why the contract says they are ignored rather than leaving it open.

## One pass with a remembered sign

seen = 0 for each interior vertex i: s = sign of cross(p[i-1], p[i], p[i+1]) if s == 0: continue if seen == 0: seen = s else if s != seen: answer NO answer YES

Each s is #2271's orientation of three consecutive points. The loop runs over i from 1 to n-2, because a turn needs a point before and a point after, so the first and last points never contribute.

## Why this is the convexity test, and what it is not

A closed polygon is convex exactly when all its turns go the same way, so this is the core of a convexity check. Two things stop it from being a complete one.

It tests a PATH, not a closed polygon: a closed polygon has n turns including the two that use the wrap, and this problem has n - 2. #2274 discusses the same wrap for the area sum.

And a closed path whose turns all go the same way can still fail to be a simple polygon, because it may wind around more than once, like a pentagram. The turn test alone cannot see that. So "all turns agree" is necessary for convexity and not sufficient without also knowing the path closes and winds once.

Being precise about that is the point of making this a path rather than claiming it decides convexity.

## The degenerate sizes

With n <= 2 there are no interior vertices, so the loop body never runs and the answer is YES. With n = 3 there is exactly one turn, and one sign can never disagree with itself, so the answer is always YES whatever the points are. Both are declared tests, because a solution that initialises its remembered sign to +1 rather than to "none yet" gets the all-right-turns case wrong and still passes these.

## Width

Coordinates satisfy |x|, |y| <= 10^6, so each cross product is at most 8 * 10^12 in magnitude and needs a 64-bit integer; a signed 32-bit one stops at 2147483647 and a wrapped cross product can change sign, which turns a YES into a NO. Only the SIGN is ever used, so nothing accumulates and no sum can overflow. In JavaScript the value is below 2^53 = 9007199254740992 and a plain Number is exact.

Constraints - `1 ≤ n ≤ 200000` - `-1000000 ≤ x, y ≤ 1000000` - consecutive points need not be distinct