8854: [yosupo] Geometry - Sort Points by Argument
[Creator : ]
Description
Given $N$ 2D-points $(x_0, y_0), (x_1, y_1), \dots, (x_{N - 1}, y_{N - 1})$, please sort them by $\mathrm{atan2}(x, y)$.
In other words, sort the points in counterclockwise order that starts from the half line $x \le 0, y = 0$.
Note:
- $\mathrm{atan2}(x < 0, y = 0) = \pi$.
- $\mathrm{atan2}(0, 0) = 0$.
- Points with the same argument can be ordered arbitrarily.
- The precision of the 64bit floating-point type(C++: double) may not be enough. Please use an integer-type or the 80bit floating-point type(C++: long double).
In other words, sort the points in counterclockwise order that starts from the half line $x \le 0, y = 0$.
Note:
- $\mathrm{atan2}(x < 0, y = 0) = \pi$.
- $\mathrm{atan2}(0, 0) = 0$.
- Points with the same argument can be ordered arbitrarily.
- The precision of the 64bit floating-point type(C++: double) may not be enough. Please use an integer-type or the 80bit floating-point type(C++: long double).
Input
$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$
Constraints
- $1 \leq N \leq 200,000$
- $|x_i|, |y_i| \leq 10^9$
- $x_i, y_i$ are integers.
- $|x_i|, |y_i| \leq 10^9$
- $x_i, y_i$ are integers.
Sample 1 Input
8
1 0
0 0
-1 0
0 1
0 -1
1 1
2 2
-10 -1
Sample 1 Output
-10 -1
0 -1
1 0
0 0
1 1
2 2
0 1
-1 0