Convex Layers

AC一覧

Problem Statement
問題文

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

二次元平面上の異なる $N$ 個の点 $(x_0, y_0), (x_1, y_1), \dots, (x_{N - 1}, y_{N - 1})$ が与えられます。凸包(及びその辺上)に含まれる点をすべて削除する、という操作を全ての点が消えるまで繰り返します。 各点について、何度目の操作で点が削除されるかを答えてください。

注意:

  • 同一直線上に複数の点が存在している可能性もあります。

Constraints
制約

Input
入力

$N$
$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_i$ represents the iteration the $i$th point was removed.

Sample
サンプル

# 1

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

# 2

1
1000000 1000000
1

# 3

2
0 0
1000000 1000000
1
1

# 4

4
0 0
0 1000000
1000000 0
1000000 1000000
1
1
1
1

# 5

5
0 0
0 1000000
1000000 0
1000000 1000000
123456 654321
1
1
1
1
2

# 6

6
0 0
0 1000000
1000000 0
1000000 1000000
123456 234567
345678 456789
1
1
1
1
2
2

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions