← 返回题目列表

AtCoder · abc348_b

C. 最远点

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

关于 xy-平面,有 N 点的 ID 号来自 1 to 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
  • (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
  • 所有输入值均为整数。

输入

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

输出

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


示例输入 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 和 2,并点 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