整数座標の N+2 ポイントが与えられます。そのうちの 2 つは基点です。指定された基点を通る 2 本の平行線を引く必要があります。2 本の平行線の間に位置する点の最大数は? 私の英語で申し訳ありませんが、事前に感謝します！
次の図では、赤い点が基点で、黒い点が通常の点です。黄色の領域は、ブラック ポイントの最大数が必要な場所です。黒い点の 1 つが線の 1 つにある場合、この点は線の間にあると見なされます。
http://i.stack.imgur.com/Awhg6.png
時間の複雑さ O(N*N) で解決策を見つけましたが、これは遅すぎます。
2 本の線が両方の基点を通過していると想像してください。線の間のストリップの幅は 0 で、内側に点はありません (または、「内側」の定義によっては、いくつかの点があります)。
次に、2 本の線が平行を保ちながら反時計回りにゆっくりと回転するとします。半回転を終えると、元の位置に戻ります。ラインが回転すると、ポイントを通過し、ライン間のストリップに出入りします。
線が単位時間あたり一定数の回転を行うと仮定して、点ごとに、線の間のストリップに入る時間と、ストリップから出る時間を計算します。(これらの時間は基本的に角度です)。両方の種類のイベントを一緒に並べ替えます。次に、各エントリ イベントに対して +1 をカウントし、各終了イベントに対して -1 をカウントして、イベントを調べます。まったく同じ時間に発生するイベントについては、「内部」の定義に応じて、最初に -1 または +1 を実行します。最大数を追跡します。
