凸层

【题目描述】

给定 $N$ 个互不相同的二维点 $(x_0, y_0), (x_1, y_1), \dots, (x_{N - 1}, y_{N - 1})$。只要还有点剩余，就删除剩余点集的凸包边界上的所有点。

对每个点，求出它在第几轮被删除。

注意：

• 点可能共线

【输入】

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

【输出】

对每个点，输出它在第几轮被删除。

$l_0$
$l_1$
:
$l_{N - 1}$

$l_i$ 表示第 $i$ 个点被删除的轮次。

【输入样例】

6
0 0
0 1
0 2
1 1
2 1
3 1

【输出样例】

1
1
1
2
2
1

【输入样例2】

1
1000000 1000000

【输出样例2】

1

【输入样例3】

2
0 0
1000000 1000000

【输出样例3】

1
1

【输入样例4】

4
0 0
0 1000000
1000000 0
1000000 1000000

【输出样例4】

1
1
1
1

【输入样例5】

5
0 0
0 1000000
1000000 0
1000000 1000000
123456 654321

【输出样例5】

1
1
1
1
2

【输入样例6】

6
0 0
0 1000000
1000000 0
1000000 1000000
123456 234567
345678 456789

【输出样例6】

1
1
1
1
2
2

【数据范围】

• $1 \leq N \leq 200000$
• $0 \leq x_i, y_i \leq 1000000$
• $x_i, y_i$ 为整数。

【来源】

Library Checker（yosupo06） convex_layers