[R15B]最近点 - 代码源竞赛平台

时空限制

1S/512M

题目描述

二维平面上有 $n$ 个点，点 $i$ 的坐标为 $(x_i,y_i)$。

定义点 $i$ 和点 $j$ 的距离为 $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$。

对于 $i=1\sim n$ 分别求出，除点 $i$ 外距离点 $i$ 最近的点的编号。如果距离最近的点有多个，输出其中编号最小的。

格式

输入格式

第一行包含一个整数 $n$，表示点的数量。

接下来 $n$ 行每行包含两个整数 $x_i,y_i$，表示点 $i$ 的坐标。

输出格式

输出 $n$ 个整数，分别表示对 $i=1\sim n$，除点 $i$ 外距离点 $i$ 最近的点的编号。如果距离最近的点有多个，输出其中编号最小的。

样例

样例输入 #1

5
1 1
5 1
3 3
5 5
1 5

样例输出 #1

3 3 1 3 3

样例输入 #2

4
2 2
1 2
2 1
2 2

样例输出 #2

4 1 1 1

数据规模

对于 $100\%$ 的数据，$2\leq n\leq 2000$，$1\leq x_i,y_i\leq 1000$。