問題タブ [closest-points]

まず、トップコーダーで O(N lgN) 時間で最も近いポイントのペアを見つけるためのスイープラインアルゴリズムについて読んでいました。私はアルゴリズムをほとんど理解していましたが、ここで提供されている実装(以下にコピーして読みやすくしています) を見ると、いくつかの顕著な違いに気付きました。

まず、上記の実装スニペットでは、ポイントを保持し、外接する四角形を表す std::set は、(x 座標ではなく) y 座標によって並べ替えられていませんThe set is ordered by y coordinate. (Topcoder)。

次に、セットが y 座標でソートされていなくても、イテレータを に使用するとconsider points in the active set ... whose y coordinates are in the range yN − h to yN + h、 の下限と見なされpll(points[i].y - shortestDistSoFar, points[i].x - shortestDistSoFar)ます。なぜy最初に来るのですか？正しい順序になると思いますが、pll(points[i].x, points[i].y - shortestDistSoFar)これに変更するとアルゴリズムが壊れます。

誰かがこれらの一見矛盾したことに対処するのを手伝ってくれませんか?

最初に; 私はこれを学校の課題として行っています。そのため、スイープ ライン アルゴリズムを使用しています。私は先生から与えられた疑似コードに基づいています。

同じ機能を提供すると言われた平衡二分探索木の代わりに、TreeMap を使用して独自の実装を行いました。（これが本当かどうかはわかりませんが？）

ただし、適切な最終結果が得られず、その理由が本当にわかりません。私は自分自身を盲目的に見つめてきました。

以下は、実際の計算を実行するコードの一部です。ポイントリストの作成やその他の重要でないものは省略しました。

編集: 疑似コードはhttp://pastebin.com/i0XbPp1aにあります。これは、先生がホワイトボードに書いたものから取ったメモに基づいています。

結果について: 次のポイント (X, Y) を使用: (0, 2) - (6, 67) - (43, 71) - (39, 107) - (189, 140)

~36 になるはずですが、~65 になっています。

私は現在、(x,y) 座標系で最も近い点のペアを見つけるための C++ プログラムを作成するように割り当てられています。しかし、私は一つのことを理解しようとするのに苦労しています。

最も近いペアの問題について読んだすべてのチュートリアル/ガイドでは、ポイントのセットをY座標でソートするように指示されていますが、これのポイントがわかりませんか? Y座標でソートする理由とその用途を誰かに説明してもらえますか? L と X* を取得するためにポイントを X でソートすることは理解していますが、ポイントを Y 座標でもソートする必要がある理由がわかりません。

最も近い点のペアを見つけようとしていますが、コードが機能しません。私はこの分野の専門家ではありません。助けてください。これは私のプロジェクト用ですT_T

私のコードは次のようになります：

そこで。私はかなり悪いですよね？T_T