分数: 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