algorithm - 特定の条件を満たすセットの要素のすべての組み合わせを見つける

Question

ここに私が解決しようとしている問題があります: 勾配 m と定数 c を持つ一連の直線が与えられています。ここで、y 軸の右側で交差するこれらの線の交点の数を見つける必要があります。これは基本的に、1行目と2行目で

                    c1>c2 and m2>m1

y 軸の右側の交点の総数をカウントする O(nlogn) アルゴリズムが必要です (アルゴリズムが存在する場合)。o(n2) アルゴリズムを取得するためにいつでも総当たりを行うことができますが、より高速なアルゴリズムを探しています。

Answer 1

実装がより簡単だと思うので、ソリューションを投稿しています。

Line のオブジェクトを取得し、次の属性が定義されているとします。

- m (slope,    initialized on start)
- c (constant, initialized on start) 
- pos_m ( default 0 value )
- pos_c ( default 0 value )

Vこれで、これらの行のベクトルが 得られます。

1. V要素のキーm(O(nlogn)) を使用して並べ替えます。
2. VインデックスiセットV[i].pos_m = i(O(n))で反復します。
3. V要素のキーc(O(nlogn)) を使用して並べ替えます。
4. Vインデックスiセットで繰り返しV[i].pos_c = iます。（の上））。
5. インデックスdo (O( n ))result = 0を反復処理します。Viresult += | V[i].pos_m - V[i].pos_c |

並べ替えで、比較した値が等しい場合は、もう一方のキーを使用して順序を決定します (両方が等しい場合、それらは同じ行です)。たとえば、1. 2 つの線の傾きが同じ場合、定数を決定要因にします。