Sort Points by Argument

AC一覧

Problem Statement問題文

Given a size $N$ 2D-point sequence $(x_0, y_0), (x_1, y_1), \dots, (x_{N - 1}, y_{N - 1})$. Sort this by $\mathrm{atan2}(x, y)$. In other words, sort points in counter-clock-wise order that starts with a half line $x \le 0, y = 0$.

Note:

• $\mathrm{atan2}(x < 0, y = 0) = \pi$.
• $\mathrm{atan2}(0, 0) = 0$.
• We don't specify the order of same argument points.
• 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).

• $\mathrm{atan2}(x < 0, y = 0) = \pi$ とする
• $\mathrm{atan2}(0, 0) = 0$ とする
• 同じ角度の点同士の順番は任意
• 64bit浮動小数(double)を使うと誤差によりWAになるかもしれません、整数か80bit浮動小数(long double)を使ってください

Constraints制約

• $1 \leq N \leq 200{,}000$
• $|x_i|, |y_i| \leq 10^{9}$
• $x_i, y_i$ are integers.

Input入力

$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$


Output出力

$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$


Sampleサンプル

# 1

8
1 0
0 0
-1 0
0 1
0 -1
1 1
2 2
-10 -1

-10 -1
0 -1
1 0
0 0
1 1
2 2
0 1
-1 0


Timelimit: 5 secs

Before submitting, please confirm terms and conditions