配点 : 100 点
問題文
2 在维度平面上 N 点 有 P_1,P_2,\dots,P_N 第i 点是 它位于 (X_i, Y_i) 。现在您可以根据需要多次重复以下操作。 (操作 1 您也可以选择根本不执行此操作。 ) 选择
- 1 以上 N-2 的整数 i 。之后,P_i 和 在 P_{i+2} 的中点 移动到与 M , 输出P_{i+1} 在 M 对称的点。
点 P_1 和点 P_i 距离 比方说 D_i 。这时, 求i=2,3,\dots,N , 从未连接到D_i^2 的最大可能值。
制約
- 3 \le N \le 2000
- - 2 \times {10}^5 \le X_i, Y_i \le 2 \times {10}^5
- P_{i} \neq P_{i+1} \ (1 \leq i \leq N-1)
- 所有输入均为整数。 将
小課題
- (2 点) N = 3
- (3 点) N \leq 7
- (15 点) N \leq 20
- (15 点) N \leq 40,-40 \leq X_i,Y_i \leq 40
- (35 点) N \leq 200
- (30 点)无附加约束
入力
输入是按以下格式从标准输入给出的。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
N-1 行。 打印第 i 行中,{D_{i+1}}^2 的最大可能值打印为整数。 考虑执行
入力例 1
3 0 0 1 1 2 0
出力例 1
2 4
i=1 操作。点 P_1 和点 P_3 的中点是 (1,0) 。因此,要点 转至 P_2 是 给出了 (1,-1) 。这时,{D_2}^2 = 2,{D_3}^2 = 4 。
入力例 2
4 0 0 1 0 0 1 1 1
出力例 2
2 4 2