8855: [yosupo] Geometry - Convex Layers
[Creator : ]
Description
You are given $N$ distinct 2D-points $(x_0, y_0), (x_1, y_1), \dots, (x_{N - 1}, y_{N - 1})$. While there are points remaining, remove all points on the boundary of the convex hull of the remaining points.
For each point, determine which iteration it was removed in.
Note:
- Points may be collinear
For each point, determine which iteration it was removed in.
Note:
- Points may be collinear
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}$
Output
For each point, output which iteration it was removed in.
$l_0$
$l_1$
:
$l_{N - 1}$
$l_0$
$l_1$
:
$l_{N - 1}$
Constraints
- $1 \leq N \leq 200,000$
- $0 \leq x_i, y_i \leq 10^6$
- $x_i, y_i$ are integers.
- $0 \leq x_i, y_i \leq 10^6$
- $x_i, y_i$ are integers.
Sample 1 Input
6
0 0
0 1
0 2
1 1
2 1
3 1
Sample 1 Output
1
1
1
2
2
1
Sample 2 Input
1
1000000 1000000
Sample 2 Output
1
Sample 3 Input
2
0 0
1000000 1000000
Sample 3 Output
1
1
4
0 0
0 1000000
1000000 0
1000000 1000000
1
1
1
1
Sample 4 Input
6
0 0
0 1000000
1000000 0
1000000 1000000
123456 234567
345678 456789
Sample 4 Output
1
1
1
1
2
2
HINT
相同题目：yosupo。