问题描述

给定 $N$ 个互异的二维点 $(x_0, y_0), (x_1, y_1), \dots, (x_{N-1}, y_{N-1})$。
只要仍有剩余点，就反复移除当前剩余点集的凸包边界上的所有点。
对每个点，确定其在第几轮迭代中被移除。

注意：

• 点可能共线。

约束条件

• $1 \le N \le 2 \times 10^5$
• $0 \le x_i, y_i \le 10^6$
• $x_i, y_i$ 为整数。

输入

N
x₀ y₀
x₁ y₁
:
x_{N-1} y_{N-1}

输出

对每个点，输出其被移除的迭代轮次：

l₀
l₁
:
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

1
1000000 1000000

1

2
0 0
1000000 1000000

1
1

4
0 0
0 1000000
1000000 0
1000000 1000000

1
1
1
1

5
0 0
0 1000000
1000000 0
1000000 1000000
123456 654321

1
1
1
1
2

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

1
1
1
1
2
2