B. [R15B]最近点

    Type: Default 1000ms 512MiB

[R15B]最近点

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

二维平面上有 nn 个点,点 ii 的坐标为 (xi,yi)(x_i,y_i)

定义点 ii 和点 jj 的距离为 (xixj)2+(yiyj)2\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}

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

格式

输入格式

第一行包含一个整数 nn,表示点的数量。

接下来 nn 行每行包含两个整数 xi,yix_i,y_i,表示点 ii 的坐标。

输出格式

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

样例

样例输入 #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%100\% 的数据,2n20002\leq n\leq 20001xi,yi10001\leq x_i,y_i\leq 1000

代码源挑战赛 Round 15

Not Attended
Status
Done
Rule
DMY
Problem
6
Start at
2025-6-6 20:00
End at
2025-6-6 21:30
Duration
1.5 hour(s)
Host
Partic.
579