004 - 2点間の最小距離

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 0 /


TLE
1sec
MLE
64MB
得点
100

問題

 平面上の 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≦108 かつ -10000≦x≦10000, -10000≦y≦10000 とし, 5つの入力ファイルのうち3つでは n≦100 である. また,どの入力ファイルにおいても,全ての座標は異なるものとする.

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

入力例1 入力例2
2 3
0 0 5 5
1 1 0 0
-3 -4
 
出力例1 出力例2
2 25