2277. Sorting Points by Angle Without Trigonometry

Given n points, none of them the origin, print them sorted by the angle of the ray from the origin to the point, going ANTICLOCKWISE starting from the positive x axis. Points on the same ray are ordered by distance from the origin, nearest first.

(1,0) (0,1) (-1,0) (0,-1) -> (1,0) (0,1) (-1,0) (0,-1) (0,1) (1,0) (0,-1) (-1,0) (1,1) -> (1,0) (1,1) (0,1) (-1,0) (0,-1) (2,0) (1,0) (-2,0) (-1,0) -> (1,0) (2,0) (-1,0) (-2,0)

The angle of the positive x axis is 0 and angles increase anticlockwise up to but not including a full turn, so a point on the positive x axis sorts first and a point just below it sorts last.

## What most people try first

atan2(y, x) as a sort key. It is the obvious thing and it has three problems.

It returns a double, so two points on the same ray at different distances may get keys that are equal, or that differ by one bit in an unpredictable direction, and the tie-break the problem asks for becomes unreliable.

It returns values in (-pi, pi], not [0, 2 * pi), so a point just below the positive x axis comes out with a key near -pi... actually near 0^-, and a point just above the negative x axis comes out near +pi. Fixing the range means adding 2 * pi to the negatives, which introduces another rounding.

And it is slow: a transcendental function per point, where a comparison needs only multiplications.

The deeper objection is the one this whole topic is built on. The ORDER of two points by angle is an exact, decidable fact about integers. Computing an approximate angle for each and then comparing the approximations can only lose information.

## Compare two points directly, with a cross product

The cross product Px * Qy - Py * Qx is positive when Q is anticlockwise from P by less than half a turn, negative when it is clockwise by less than half a turn, and zero when the two are on the same line through the origin.

That is almost a comparator, and it is not transitive on its own: with three points spread more than half a turn apart, each can be "anticlockwise from" the next. The standard repair is to split the plane into two halves first.

half(P) = 0 if Py > 0, or (Py == 0 and Px > 0) angles in [0, pi) = 1 otherwise angles in [pi, 2pi)

Within one half, any two points are less than half a turn apart, so the cross product IS a consistent comparator there. So:

compare(P, Q): if half(P) != half(Q): the smaller half comes first c = Px * Qy - Py * Qx if c != 0: positive means P comes first otherwise they are on the same ray: the smaller squared distance first

## Why the half-plane boundary is where it is

The boundary has to fall exactly at angle 0 and at angle pi. The condition Py > 0 or (Py == 0 and Px > 0) puts the positive x axis in half 0, which the problem requires since angle 0 sorts first, and puts the negative x axis in half 1, since there Py == 0 and Px < 0.

Getting that condition wrong by using Py >= 0 instead would put the NEGATIVE x axis in half 0 as well, and then within half 0 two points at angles 0 and pi are exactly half a turn apart, where the cross product is 0 and the comparator falls through to the distance tie-break. The result is that (-1,0) and (1,0) get ordered by distance rather than by angle. The declared test (2,0) (1,0) (-2,0) (-1,0) is there for exactly that: the required answer is (1,0) (2,0) (-1,0) (-2,0) and the Py >= 0 version produces (1,0) (2,0) (-2,0) (-1,0) or worse.

## Why the tie-break makes the answer unique

Without it, points on the same ray could come out in any order and the expected output would not be well defined. Ordering them by squared distance fixes a single correct answer. Two IDENTICAL points compare equal, which is harmless: they print the same bytes either way.

The squared distance is used rather than the distance for the usual reason. It is an integer, so the comparison is exact, and the square root would be irrational and would add nothing, since squaring is monotone on non-negative numbers and therefore preserves the order.

## Width

Coordinates satisfy |x|, |y| <= 10^6, so the comparator's cross product Px * Qy - Py * Qx is at most 2 * 10^12 in magnitude and a squared distance is at most 2 * 10^12. Both need a 64-bit integer, since a signed 32-bit one stops at 2147483647, and a wrapped cross product in a comparator does not merely give a wrong answer: it can make the comparator inconsistent, which in C++ is undefined behaviour inside std::sort and can crash rather than mis-sort.

In JavaScript both quantities are below 2^53 = 9007199254740992, so a plain Number is exact and the comparator is safe.

Constraints - `1 ≤ n ≤ 200000` - `-1000000 ≤ x, y ≤ 1000000` - no point is `(0, 0)` - points may repeat