第５回日本情報オリンピック　模擬試験１

2005年11月7日
情報オリンピック日本委員会

問題 ４

　平面上の 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 である． また，どの入力ファイルにおいても，全ての座標は異なるものとする．

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

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