n個の点（x、y）の集合が与えられた場合、O（n logn）時間内にそれらの間に負の勾配を持つ点の対の数を見つけることは可能ですか？

Question

(x,y)という形の2次元平面上のn点の集合を考えると、2点を結ぶ線が負の傾きを持つように、すべての点の対の数を見つけることが目的です。(xi,yi)と(xj, yj)

xiの2つが同じ値を持たないとします。すべての点が[-100,100]または他の範囲内にあるとします。

Answer 1

あなたが尋ねるのは、xに関してポイントをソートするときに得られるyの配列の非反転の数を見つけることに相当します。あなたはこの並べ替えを行うことができます - それはO(n log n)です。

私はその反転がi>jとa[i] < a[j]であることを思い出させます。私が言っている同等性は、証明するのは簡単です。

6ポイント（4,4）、（2,1）、（6,6）、（3）、（5,2）、（1,5）があるとします。 xに関してソートした後、（1,5）、（2,1）、（3,3）、（4,4）、（5,2）、（6,6）が得られます。負の傾きは、<（2,1）、（3,3）>、<（2,1）、（4,4）>、<（2,1）、（5,2） >、<（2,1）、（6,6）>等である。yが反転していないすべてのペア。

O(n log n)マージソートアルゴリズムの拡張を使用して逆数を数えることができます。基本的には、右の部分配列（大きなインデックスを含むもの）の値を加算するたびに反転のカウンタを増やすだけです。左側の部分配列からまだ処理されていない値の量で、反転回数を増やします。

ここでは、反転の回数をカウントする例を示します。

Initial array 5 1 3 4 2 6 inv := 0 // Total inversions: 6 
merge step 1: <5 1 3> <4 2 6> inv = 0 
merge step 2: <5> <1 3> | <4> <2 6> inv = 0 
merge step 3: <5> [<1> <3>] | <4> [<2> <6>] inv = 0 
merge step 4: <5> <1 3> | <4> <2 6> inv = 0 // both pairs were already sorted 
merge step 5: <1 3 5> | <2 4 6> inv = 3 // we add one for 1, 3 and 2 
merge step 6 <1 2 3 4 5 6> inv = 6 // we add 2 (3 and 5) for 2 and 1 for 4 

あなたが反転回数にペア(n * (n - 1))/2の総数マイナス反転invの数の非反転回数を見つけた後。

例の場合、これは6 * 5/2 - 6 = 9です。