AT_pakencamp_2025_day2_f Symmetry Point

$ 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 $ として考えられる最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $

$ N-1 $ 行出力せよ。 $ i $ 行目には、 $ {D_{i+1}}^2 $ として考えられる最大値を整数で出力せよ。

### 小課題 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 $ 点) 追加の制約はない ### Sample Explanation 1 $ i=1 $ として操作を行うことを考えます。点 $ P_1 $ と点 $ P_3 $ の中点は $ (1,0) $ となります。よって、点 $ P_2 $ は $ (1,-1) $ に移動します。この時、 $ {D_2}^2 = 2,{D_3}^2 = 4 $ となります。 ### Constraints - $ 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) $ - 入力はすべて整数である。