[問題案] Closest Pair of Points

[SSRS-cp]

問題名: Closest Pair of Points

問題

座標平面上に $N$ 個の点がある。$i$ 番目の点の座標は $(x_i, y_i)$ である。距離が最も近い $2$ 点間の距離と、それらの番号を出力せよ。

入力

N x_0 y_0 x_1 y_1 ... x_{N-1} y_{N-1}

出力

ans i j

制約

2≦N≦500000 |x_i|, |y_i|≦10^9

メモ

・座標を distinct にするか ・許容誤差は？

[shirotsume4]

距離の2乗を出力させるようにすると誤差の心配がなくなると思うのですが、どうですか

あるいは、距離は出力させず点対の番号だけ出力させるようにするのはどうでしょうか

[SSRS-cp]

誤差ジャッジをできるだけ回避したいという方針で進めるならばのようになるでしょうが、誤差ジャッジを回避することができない問題もあるので、いずれは誤差ジャッジを導入することになると思います。これを考慮すると、わざわざ小数出力を回避するために少し不自然な出力形式を取る必要はないという考えがありました。

当然、誤差なく出力できる方法がある場合はなるべくそのようにするという方針も考えられます。

[SSRS-cp]

問題名　Closest Pair of Points のほうがよいかもしれません

[maspypy]

少なくとも当面は、小数出力は厳しそうなので、作るなら頂点番号2つ出力でお願いします。