2本の平行線の間の最大点数

Question

N + 2点に整数座標が与えられています。それらの2つは基点です。与えられた基点を通って2本の平行線を引く必要があります。 2本の平行線の間にあるポイントの最大数はいくらですか？私の英語のために申し訳ありませんし、事前に感謝！

以下の図では、REDドットがベースポイント、BLACKがノーマルポイントです。黄色の領域は、黒点の最大数が必要な場所です。黒点の1つが線の1つにONである場合、この点が線の間にあるとみなされます。

http://i.stack.imgur.com/Awhg6.png

私は、時間の複雑さO（N * N）での解決策を見つけたが、これは遅すぎます。

Answer 1

2本の線が両方の基点を通過するとします。線の間のストリップの幅は0で、内部にポイントはありません（または、 "内側"の定義に応じていくつかのポイントがあります）。

ここで、2つの線が反時計回りにゆっくりと回転しているとします。半分のターンを終えると、彼らは以前と同じポジションにいます。線が回転するにつれて、点を通過し、線の間に線を入れたり線から離したりします。

各行が単位時間当たり一定の回転数を有すると仮定すると、各点について、線の間に線に入る時間と、線を離れる時間を計算する。 （これらの時間は基本的にアングルです）。両方の種類のイベントを並べ替えます。今度は、各エントリイベントの+1と各終了イベントの-1をカウントしてイベントを調べます。同じ正確な時刻に発生するイベントについては、「内側」の定義に応じて、最初に-1または最初に+1します。最大数を記録する。