兩條平行線之間的最大點數

-3

我給出了帶整數座標的N + 2個點。其中2個是基點。需要通過給定的基點繪製兩條平行線。兩條平行線之間的最大點數是多少？對不起，我的英語，並提前致謝！兩條平行線之間的最大點數

在下圖中，紅點是基點，黑點是基準點。黃色區域是黑點最多的地方。如果其中一個黑點在其中一條線上，則認爲該點位於線條之間。

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

我發現，在時間複雜度爲O解決方案（N * N），但是這是太慢了。

2012-04-26 user1359532

您的意思是「連接這兩條線的線上的最大點數」？如果是這樣，它是否必須垂直於它們？如果垂直，那麼它將與線條之間的距離相同。否則，您可以計算角點之間的距離，並選擇最長的。如果你不是在談論某一方面的問題，那麼我們可能需要更多的解釋。 – 2012-04-26 19:20:14

是否需要遵循C++的問題？ – 2012-04-26 19:25:59

致下流者：這是一個合理的問題。也許是錯誤的，並沒有表現出自己的努力的跡象，但既不是外在的也不是「不是真正的問題」。 – 2012-04-26 19:45:19

想象一下，你的兩條線穿過兩個基點。線條之間的條的寬度爲0，並且裏面沒有點（或者有一些點，這取決於「內部」的定義）。

現在想象兩條線緩慢地逆時針旋轉，同時保持平行。完成半圈後，他們與之前的位置相同。隨着線條旋轉，它們穿過你的點，從而進入和離開線條之間的條。

假設線條每單位時間產生一定數量的旋轉，對於每個點計算它在線條之間進入條帶的時間以及它離開條帶的時間。（這些時間基本上是角度）。將兩種事件排序在一起。現在仔細查看事件，爲每個輸入事件計數+1，每個輸出事件計數爲-1。對於同一時間發生的事件，請先執行-1或先執行+1，具體取決於「內部」的定義。跟蹤最大數量。

來源

2012-04-26 19:42:51

兩條平行線之間的最大點數

回答

相關問題