htkb-proconの日記

初心者がPythonで問題解いた記録

AOJ 0585 Nearest Two Points 最近点対問題

距離が最小の2点 | Aizu Online Judge

この問題、適当に証明もせずなんとなく思いつきでコードを書いて提出したら通ってしまって、CPU時間のランキングを見てみるとC++Javaのコードに囲まれていておっかしいなーと思ってたんだけど、ちょっと考えてみたら自明に嘘解法だった。ていうかなんでこんなのが通るの?

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2914496

上のコードはx軸でソートしてx軸で隣り合う点同士の距離を取っていき、次にy軸でソートしてy軸で隣り合う点同士の距離を取っていき、最小値を出力するだけ。当然ながらx軸でもy軸でも隣り合わない点対が最近だった場合は正しい答えが出ず、

4
1 3
2 100
3 1
100 2

のテストケースだと9410を出力してしまう。最近点対問題は典型問題のようなのでちゃんと知っとかないとまずいなっと思い色々調べたところ、基礎的な考え方について一番わかりやすかったのはなんと蟻本(p324〜)だった。上級編のとこだったから100年早いと思って読んでなかったよ……。

x軸で再帰的に左右に分割していき、分割したそれぞれの領域内の最近点対距離で最小dを得て、x軸の中央値から±dの範囲内について分割境界をまたぐ点対が最短にならないかチェックする、というのが図で示してあって分かりやすかった。ただし、与えられた全ての点のx座標が同じ、などのようないじわるなテストケースについてのフォローがなく、そのようなケースだと境界をまたぐ点対チェックでO(N2)になっちゃう?のかな?中央値±dの範囲に全ての点が含まれてしまうので、渡された点のx座標を重複なしのsetで取り数を数え、半分以上被ってたら基準軸をy軸に切り替えるなどの工夫をする必要があった。

ACコードはこれ http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2917868

axis1を基準にleftrightに分割し再帰していき、境界をまたいで最近点対になる可能性のある点をmid_aに取って各点+dまでの範囲について点対距離をチェックしていく。itertools.takewhileが便利だった。

ただこの問題は5つしかテストケースがなく全部同じx座標/y座標のようなコーナーケースも含まれず、逆にNは大きくLLでは定数倍改善ゲームになりがちなので、まずは下の問題を通すのから始めたほうがいいかも。

最近点対 | 計算幾何学 | Aizu Online Judge

ACコード http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2917884

こっちはいじわるなケース完備なので、ちゃんと軸を変えていかないとめっちゃTLEする。