AT_abc348_b [ABC348B] Farthest Point

题目描述

在 $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$ $\cdots$ $X_N$ $Y_N$

输出格式

输出共 $N$ 行。第 $i$ 行输出从点 $i$ 到距离最远的点的编号。

输入输出样例 #1

输入 #1

4
0 0
2 4
5 0
3 4

输出 #1

3
3
1
1

输入输出样例 #2

输入 #2

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

输出 #2

6
6
6
6
6
4

说明/提示

限制

• $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)$
• 所有输入均为整数。

样例解释 1

点如下图所示。这里 $P_i$ 代表点 $i$。  从点 $1$ 到最远点的距离为点 $3$ 和点 $4$，其中编号较小的是点 $3$。从点 $2$ 到最远点的距离为点 $3$。从点 $3$ 到最远点的距离为点 $1$ 和点 $2$，其中编号较小的是点 $1$。从点 $4$ 到最远点的距离为点 $1$。