← 返回题目列表

AtCoder · pakencamp_2025_day2_f

F. 对称点

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

配点 : 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)
  • 所有输入均为整数。 将

小課題

  1. (2 点) N = 3
  2. (3 点) N \leq 7
  3. (15 点) N \leq 20
  4. (15 点) N \leq 40,-40 \leq X_i,Y_i \leq 40
  5. (35 点) N \leq 200
  6. (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