The Oldest Site

Time Limit : 5 sec, Memory Limit : 65536 KB

最古の遺跡

問題

昔, そこには集落があり, 多くの人が暮らしていた. 人々は形も大きさも様々な建 物を建てた. だが, それらの建造物は既に失われ, 文献と, 遺跡から見つかった柱だけ が建造物の位置を知る手がかりだった.

文献には神殿の記述がある. 神殿は上から見ると正確に正方形になっており, その 四隅には柱があった. 神殿がどの向きを向いていたかはわからない. また, 辺上や内 部に柱があったかどうかもわからない. 考古学者たちは, 遺跡から見つかった柱の中 で, 正方形になっているもののうち, 面積が最大のものが神殿に違いないと考えた.

柱の位置の座標が与えられるので, 4 本の柱でできる正方形のうち面積が最大のも のを探し, その面積を出力するプログラムを書け. なお, 正方形の辺は座標軸に平行 とは限らないことに注意せよ.

下の図の例では, 10 本の柱があり, 座標 (4, 2), (5, 2), (5, 3), (4, 3) にある 4 本と座 標 (1, 1), (4, 0), (5, 3), (2, 4) にある 4 本が正方形をなしている. 面積が最大の正方形 は後者で, その面積は 10 である.

入力

入力ファイルのファイル名は input.txt である. 1 行目には, 遺跡から見つかった柱の本数 n が書かれている.

2 行目から n + 1 行目までの n 行の各々には, 柱の x 座標と y 座標が空白区切り で書かれている.

1 本の柱が 2 度以上現れることはない.

n は 1 ≤ n ≤ 3000 を満たす整数であり, 柱の x 座標と y 座標は 0 以上 5000 以 下の整数である.

採点用データのうち, 配点の 30% 分は 1 ≤ n ≤ 100 を満たし, 配点の 60% 分は 1 ≤ n ≤ 500 を満たす.

出力

出力ファイルのファイル名は output.txt である.

出力ファイルには 1 個の整数を出力する. 4 本の柱からなる正方形が存在する場 合は, そのような正方形のうち面積が最大のものの面積を出力し, そのような正方形 が存在しない場合は 0 を出力せよ.

入出力の例

例に対応する入出力は以下の通りである.

input.txt

10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2

output.txt

10

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

Notes on Submission

標準入出力を行うプログラムを作成して下さい.

上記形式で複数のデータセットが与えられます. データセットの終わりは1つのゼロを含む行で示されます.

Sample Input

10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
0

Sample Output

10
10

Source: 7th Japanese Olympiad in Informatics , 2007-02-12
http://www.ioi-jp.org/