最远点

题目描述

在 $xy$ 平面上有 $N$ 个点,编号为 $1$ 到 $N$。点 $i$ 位于坐标 $(X_i, Y_i)$,且不存在两个坐标相同的点。

从每个点出发,找出离它最远的点,并输出该点的编号。

若最远的点有多个,则输出其中编号最小的那个。

这里使用欧几里得距离:对于两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$,它们之间的距离为 $\sqrt{(x_1-x_2)^{2}+(y_1-y_2)^{2}}$。

输入格式

输入按以下格式从标准输入给出:

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

输出格式

输出 $N$ 行。第 $i$ 行应输出离点 $i$ 最远的点的编号。

样例

4
0 0
2 4
5 0
3 4

3
3
1
1

离点 $1$ 最远的点是点 $3$ 和点 $4$,其中点 $3$ 的编号更小。

离点 $2$ 最远的点是点 $3$。

离点 $3$ 最远的点是点 $1$ 和点 $2$,其中点 $1$ 的编号更小。

离点 $4$ 最远的点是点 $1$。

6
3 2
1 6
4 5
1 3
5 5
9 8

6
6
6
6
6
4

数据范围

• $2 \le N \le 100$
• $-1000 \le X_i, Y_i \le 1000$
• 若 $i \neq j$,则 $(X_i, Y_i) \neq (X_j, Y_j)$。
• 输入均为整数。