ポジティブスロープでラインを形成することができるポイントのペアの数を見つける方法は？

Question

n組の点を考えると、正の勾配の直線を形成できる点のペアの数をどのようにして得ることができますか？

n行あり、i行目は、i番目の点のx座標とy座標を指定する2つの整数xiとyiを含みます。 2つの点は同じx座標を持ち、2つの点は同じy座標を持たない。

私の考えは、最初にxをソートし、次に各点をその下の他の点と比較することです。 でも、それはまだO（n^2）

Answer 1

xで降順にソートし、yの反転数を数えます。両方のステップはO（n log n）です。

説明正の傾きを持つ（順序付けられていない）ペアの数は、xi> xjとyi> yjのようなペア{（xi、yi）、（xj、yj）}の数です。 xで降順をソートすると、i < jの場合にxi> xjとなるようにします。 ysにおける逆変換の定義は、yi> yjとなるような対i <である。

Counting the number of inversions quickly.

Answer 2

を選んでください（ランダムに最も簡単で、予想される実行時間がありますが、線形時間で決定的に中央値点を見つけることができます）、軸を4つの象限に分割します。

x  | 
      | x x 
    x  | x 
-----------x----------- 
    x  | 
    x  |  x 
      | x 

I、II、III、IVにより左上から反時計回りに象限を表し：我々は、点THAを無視しなければならない

II | I 
----|---- 
III | IV 

軸上にある（理論的確率が0のエッジケースであり、実際には容易に処理される）。象限III形態I内のすべての点を有する正傾斜ライン内のすべての点は、同様にIIからの点がP.S.を形成しないであろう

注IV内のポイントとライン、私たちは再帰的に呼び出す：Uは組合を表し

NumPSLines(G) = |I|*|III| + 
       NumPSLines(I U II) + 
       NumPSLines(II U III) + 
       NumPSLines(III U IV) 

を。

（証明は読者に任せる）値E(|I|) = ... E(|IV|) = |G|/4 = n/4を期待ことと象限にパーティションが線形であると仮定すると、私たちを得るの予想実行時間：

そのバウンドがタイトであれば

T(n) = O(n) + 3T(n/2) 
    = O(n) + ... + 3^k * t(n/2^k) // where k = log2(n) 
    = O(log2(n) * 3^log2(n)) 
    = O(n^(log2(3)) * logn) 
    ~ O(n^1.6 * logn) 

わかりません。それについてはあまり考えていない。

このソリューションは、初めても、非常に最適化することができます。