c++ - 交差する和音のペアの COUNTING 数

Question

Nそれぞれのエンドポイントによって決定される、円内のコードを考えてみましょう。O(nlogn)円の中で交差する弦のペアの数を求める解を説明してください。

仮定: エンドポイントを共有する 2 つのコードはありません。

Answer 1

O(nlogn) でジョブを実行する一般的な線分交差アルゴリズムが存在します。
これは、2 つの弦が円の外側で交差できないため、この場合に使用できます。
次のリンクには、アルゴリズムが含まれています:
http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf

PS
基本的な計算幾何学 (ライン スイープ、レンジ ツリー) の知識が必要です。

お役に立てれば。

Answer 2

頭のてっぺんから、弦の終点を極角で並べ替えます (これは O(n log n) の部分です)。次に、並べ替えられたリスト (O(n)) を読み取ります。隣接する 2 つのエンドポイントが同じコードに属している場合、交差はありません。リスト内の 2 つの隣接するエントリが異なるコードに属している場合、これらの 2 つのコードの他のエンドポイントがどこにあるかによって、交差が発生する場合があります。たとえば、コード A にソート順でエンドポイント A1 と A2 があり、同様にコード B に B1 がある場合です。と B2 の場合、リスト内で B2-A1 を見つけることは交差ではありません。なぜなら、B1 が先で、A2 が後だからです。ただし、B1-A2 は交差点になります。

やや慎重に構築された別のソリューションについては、biziclop のコメントも参照してください。