鑑於具有N的圓限定點和M點的圓外，發現是一組N.的O之間最接近M（logN）的

Question

http://www.glassdoor.com/Interview/Google-Interview-RVW2382108.htm

我試圖來與一個溶液的點這個問題。但我還沒有成功..任何人都可以給我一個關於如何解決這個問題的提示。

我會分別拿2對2分。也就是說，我會做出2個和絃。找出他們的垂直平分線。使用這些等分線，我會找出圓的中心...

此外，我會拿出圓的方程式。找到點M與圓的交點...應該是最接近的點。但是，這一點可能存在或可能不存在於一組N點

謝謝。

Answer 1

假設圓的圓周上的點是「有序的」（即按照圍繞圓的中心的角度排序），您可以使用基於角度的二進制搜索，該搜索應達到O(log(n))範圍。

1. 從點M計算角度A到圓的中心 - O(1)。
2. 使用二進制搜索找到最大角度小於A - O(log(n))的圓周上的點I。
3. 由於圓是凸的最接近點M是I或I+1。計算兩者的距離並取最小值 - O(1)。

Answer 2

要找到最接近M的點，我們需要基於平面切割進行點的二元消除。需要對輸入點進行一些預處理，然後我們可以在O（lgn）時間內找到最接近任何給定點M的點。

1. 計算（如果沒有給出）在（R，θ）格式點的極座標表示，其中r是從中心和θ的距離爲x軸範圍（-180,180]的角度。
2. 排序的所有N個點，從x軸增加其角度的順序。

需要注意的是簡單的二進制搜索最接近於M點不會在這裏工作，比如，

• 如果給定的點排序使得θ=（-130，-100 ，-90，-23，-15,0,2,14,170），那麼對於θ= -170的點M，二分搜索將給出-130（40度距離）作爲最近點，而170（距離20度）是最接近M的點。
• 如果我們在排序時忽略了符號（認爲它會產生正確的輸出），我們新的排序數組將看起來像θ=（0,2,14,15,23,90,100,130,170），二進制搜索θ= -6的點M將產生結果應該是2或14，而0在這種情況下是最接近M的點。

要使用平面切口執行搜索操作時，

• 查找平面切割線穿過圓的中心並垂直於連接所述圓與點中心的線M.
• 消除取決於平面M的哪一半位於圓形平面的一半[90 +θ，-90 +θ）或[-90 +θ，90 +θ）。
• 將平面切割平行於第一個切口並穿過前一個平面中間的點，並消除距離M較遠的平面一半中的所有點，直到在平面的較接近一半處沒有剩餘點，在這種情況下，消除飛機的近一半。
• 保持在切割平面上，直到我們留下一個點。該點最接近M.總操作需要O（lgn）步驟。

在情況下，數據是歪斜，並在圓不能均勻地擴散，我們可以優化我們的平面切口，使得每個切口穿過其離開​​這些點的中值（根據角度）在搜索操作中。