는 N와 원 I가 용액 올 시도

Question

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

(LogN) N.의 O의 세트 중에서 M에 가장 가까운 지점을 찾아 원 밖에 지점과 지점 (M)를 정의 감안할 이 문제. 그러나 나는 성공적이지 못했습니다 ..이 문제를 어떻게 처리 할 것인지에 대한 힌트를주세요.

나는 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에 가장 가까운 점을 찾을 수있는 입력 점의 사전 처리가 필요합니다. r은 중심 θ에서의 거리 (지정되지 않은 경우)

1. 계산 (R, θ) 형식 점 극성 표현 범위 (-180,180]의 X 축으로부터의 각도이다.
2. x 축에서 자신의 각도의 증가 순서에 정렬 모든 N 포인트. M에 점에 가장 가까운 간단한 이진 검색은 여기에 작동하지 않습니다

참고 예를 들어,

• 주어진 점 인 경우 θ = (-130, -100 , -90, -23, -15,0,2,14,170), θ = -170 인 점 M에 대해 이진 탐색은 -130 (40도 거리)을 가장 가까운 점으로, 170 (20도 멀리)
• 정렬 중에 기호를 무시하면 (올바른 출력을 생성한다고 생각하면) 새 정렬 된 배열은 θ = (0214152390100130170)처럼 보일 것입니다. θ = -6 인 점 M에 대한 이진 검색은 결과가 2 또는 14 여야하지만이 경우에는 0이 M에 가장 가까운 지점이되어야합니다.

지점으로 원의 중심을 연결하는 선으로 원의 중심을 수직 통과

• 찾기 평면 커트라인 M.
• 제거 평면 컷을 사용하여 검색 동작을 수행하도록 평면 M의 절반이 어디에 놓여 있는지에 따라 원형 평면 [90 + θ, -90 + θ)의 절반, 또는 [-90 + θ, 90 + θ]
• 첫 번째 컷과 평행하게 평면 컷을 만들고 이전 평면 중간에있는 점을 통과시키고 평면에서 더 가까운 반쪽에 점이 남지 않을 때까지 M에서 먼 평면의 모든 점을 제거합니다. 이 경우 평면의 더 가까운 절반을 제거해야합니다.
• 우리는 한 점이 남을 때까지 절단면을 계속 유지하십시오. 이 점은 M에 가장 가까운 점입니다. 전체 작업에는 O (lgn) 단계가 필요합니다. 데이터가 기울어 균일하게 원형으로 확산없는 경우

, 우리는 각각의 컷 남아있는 그 지점 (각도에 기초하여) 중간을 통과하도록 우리 평면 삭감 최적화 검색 작업에서