Nearest Two Points

Time Limit : 8 sec, Memory Limit : 65536 KB

問題 4


 平面上の n 個の点 P1, ..., Pn が与えられたとき, 距離が最小の2点を求めたい.

 入力ファイルの1行目には整数 n が書いてある. 2行目から n+1 行目のそれぞれには, 2つの正整数 x, y が1つの半角空白文字を区切りとして書いてある. i+1 行目の x, y はそれぞれ Pi の x 座標, Pi の y 座標である. これら n 点の中から最も近い2点を選んだとき, この2点間の距離の2乗を出力せよ.

 ただし, 2≤n≤500000 かつ -10000≤x≤10000, -10000≤y≤10000 とし, 5つの入力ファイルのうち3つでは n≤100 である. また,どの入力ファイルにおいても,全ての座標は異なるものとする.

出力ファイルにおいては, 出力の最後の行にも改行コードを入れること.

入出力例

入力例1

2
0 0
1 1

出力例1

2

入力例2

3
5 5
0 0
-3 -4

出力例2

25

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


Source: 5th Japanese Olympiad in Informatics, Trial Exam , 2005-11-7
http://www.ioi-jp.org/