0576 - 2点間の最小距離

問題

　平面上の n 個の点 P₁, ..., P_n が与えられたとき， 距離が最小の２点を求めたい．

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

　ただし， 2≦n≦10⁸ かつ -10000≦x≦10000, -10000≦y≦10000 とし， ５つの入力ファイルのうち３つでは n≦100 である． また，どの入力ファイルにおいても，全ての座標は異なるものとする．

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