103481: [Atcoder]ABC348 B - Farthest Point

Problem Statement

On the $xy$-plane, there are $N$ points with ID numbers from $1$ to $N$. Point $i$ is located at coordinates $(X_i, Y_i)$, and no two points have the same coordinates.

From each point, find the farthest point and print its ID number. If multiple points are the farthest, print the smallest of the ID numbers of those points.

Here, we use the Euclidean distance: for two points $(x_1,y_1)$ and $(x_2,y_2)$, the distance between them is $\sqrt{(x_1-x_2)^{2}+(y_1-y_2)^{2}}$.

Constraints

• $2 \leq N \leq 100$
• $-1000 \leq X_i, Y_i \leq 1000$
• $(X_i, Y_i) \neq (X_j, Y_j)$ if $i \neq j$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print $N$ lines. The $i$-th line should contain the ID number of the farthest point from point $i$.

Sample Input 1

4
0 0
2 4
5 0
3 4

Sample Output 1

3
3
1
1

The following figure shows the arrangement of the points. Here, $P_i$ represents point $i$. The farthest point from point $1$ are points $3$ and $4$, and point $3$ has the smaller ID number.

The farthest point from point $2$ is point $3$.

The farthest point from point $3$ are points $1$ and $4$, and point $1$ has the smaller ID number.

The farthest point from point $4$ is point $1$.

Sample Input 2

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

Sample Output 2

6
6
6
6
6
4

问题描述

在$xy$平面上，有$N$个点，ID号从$1$到$N$。点$i$位于坐标$(X_i, Y_i)$，并且没有任何两个点的坐标相同。

从每个点出发，找出最远的点并打印其ID号。如果有多个点距离相等且最远，打印这些点中ID号最小的那个。

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

限制条件

• $2 \leq N \leq 100$
• $-1000 \leq X_i, Y_i \leq 1000$
• 如果$i \neq j$，则$(X_i, Y_i) \neq (X_j, Y_j)$。
• 所有输入值都是整数。

输入

输入通过标准输入给出以下格式：

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

输出

打印$N$行。第$i$行应包含点$i$的最远点的ID号。

样例输入1

4
0 0
2 4
5 0
3 4

样例输出1

3
3
1
1

以下图展示了点的分布。$P_i$代表点$i$。 点$1$的最远点是点$3$和$4$，其中点$3$的ID号较小。

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

点$3$的最远点是点$1$和$4$，其中点$1$的ID号较小。

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

样例输入2

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

样例输出2

6
6
6
6
6
4