/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
xy 平面上に 1 から N までの番号が付いた N 個の点があります。点 i は座標 (X_i, Y_i) にあり、相異なる 2 点の座標は異なります。
各点について、その点からの距離が最大である点を求めてその点の番号を出力してください。 ただし、距離が最大である点が複数ある場合はその中で最も番号が小さい点の番号を出力してください。
ここで、距離はユークリッド距離、すなわち 2 点 (x_1,y_1) と (x_2,y_2) に対し、この 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 からの距離が最大である点の番号を出力せよ。
入力例 1
4 0 0 2 4 5 0 3 4
出力例 1
3 3 1 1
以下の図のように点が並んでいます。ここで P_i は点 i を表します。
点 1 からの距離が最大である点は点 3,4 で、その中で番号が小さいのは点 3 です。
点 2 からの距離が最大である点は点 3 です。
点 3 からの距離が最大である点は点 1,2 で、その中で番号が小さいのは点 1 です。
点 4 からの距離が最大である点は点 1 です。
入力例 2
6 3 2 1 6 4 5 1 3 5 5 9 8
出力例 2
6 6 6 6 6 4
Score: 200 points
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 2, 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