[ABC348] B - Farthest Point

B - Farthest Point

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 200 分

题面

在 平面上，有 个编号从 到 的点。第 个点位于坐标 处，并且没有两个点具有相同的坐标。

对于每个点，找到距离最远的点，并输出其编号。如果有多个距离最远的点，则输出其中编号最小的点。

这里，我们使用欧几里得距离：对于两个点 和 ，它们之间的距离为 。

限制条件

• 若 ，则 。
• 所有输入值均为整数。

---

输入

从标准输入中以以下格式给出输入数据：

输出

输出 行。第 行应包含距离点 最远的点的编号。

---

输入样例 1

4
0 0
2 4
5 0
3 4

输出样例 1

3
3
1
1

下图显示了点的排列情况。这里， 代表点 。
从点 到最远的点是点 和点 ，且点 的编号更小。

从点 到最远的点是点 。

从点 到最远的点是点 和点 ，且点 的编号更小。

从点 到最远的点是点 。

---

输入样例 2

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

输出样例 2

6
6
6
6
6
4