otrzymał koło N zdefiniowane punkty i punkt M poza kręgiem, znaleźć punkt, który jest najbliżej M spośród zbioru N. O (LogN)

Question

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

Próbowałem się z rozwiązania ten problem. Ale nie udało mi się ... Czy ktoś może mi podpowiedzieć, jak postępować z tym problemem.

Ja wezmę 2 pary po dwa punkty. Oznacza to, że zrobię 2 akordy. Znajdź ich prostopadłą dwusieczną. Używając tych dwusiecznych, znajdę środek okręgu ...

Co więcej, wymyślę równanie koła. I znajdź punkt przecięcia punktu M z okręgiem ... To powinno być najbliższe. Jednak punkt ten może lub nie może istnieć w zbiorze punktów N

Dzięki.

Answer 1

Zakładając, że punkty na obwodzie koła są "uporządkowane" (tj. Posortowane pod kątem względem środka koła), można użyć opartego na kącie wyszukiwania binarnego, które powinno uzyskać granice O(log(n)).

1. obliczyć kąt A z punktu M do środka koła - O(1).
2. Użyj wyszukiwania binarnego, aby znaleźć punkt I na obwodzie o największym kącie mniejszym niż A - O(log(n)).
3. Ponieważ kręgi są wypukłe, najbliższym punktem do M jest albo I lub I+1. Oblicz odległość do obu i weź minimum - O(1).

Answer 2

Aby znaleźć punkt najbliższy M, musimy wykonać binarną eliminację punktów na podstawie płaskich cięć. Wymagane jest nieco wstępne przetwarzanie punktów wejściowych, po którym możemy znaleźć punkt najbliższy dowolnemu punktowi M w czasie O (lgn).

1. Oblicz (jeśli nie podano) reprezentację biegunowy punktów w formie (R, θ), gdzie r jest odległością od środka i θ jest kąt od osi x, mieści się w zakresie (-180,180].
2. Sortuj wszystkie punkty N rosnące ich kąt od osi x.

pamiętać, że prosty binarny wyszukiwania punktu najbliżej M nie będzie tu pracować, np

• jeśli dana punkty posortowane w taki sposób, że θ = (-130, -100 , -90, -23, -15,0 ,2,14,170), następnie dla punktu M z θ ​​= -170, wyszukiwanie binarne da -130 (40 stopni) jako najbliższy punkt, natomiast 170 (20 stopni) jest najbliższym punktem M.
• jeśli zignorujemy znak podczas sortowania (myśląc, że da on prawidłowy wynik), nasza nowa posortowana tablica będzie wyglądać jak θ = (0,2,14,15,23,90,100,130,170), wyszukiwanie binarne dla punktu M z θ ​​= -6 da wynik równy 2 lub 14, podczas gdy 0 jest najbliższym M w tym przypadku.

Aby wykonać operację przy użyciu wyszukiwarki płaskie kawałki,

• Find płaskie cięcie Linia przechodząca przez środek okręgu i prostopadła do linii łączącej środek okręgu z punktu M.
• Wyeliminowanie połowa płaszczyzny kołowej [90 + θ, -90 + θ] lub [-90 + θ, 90 + θ] w zależności od tego, w której połowie znajduje się płaszczyzna M.
• Wykonaj płaskie cięcia równolegle do pierwszego cięcia i przechodząc przez punkt na środku poprzedniej płaszczyzny i wyeliminuj wszystkie punkty w połowie płaszczyzny dalej od M, aż w najbliższej połowie płaszczyzny nie pozostaną żadne punkty, w takim przypadku należy wyeliminować bliższą połowę płaszczyzny.
• Trzymaj się wycinania samolotów, dopóki nie zostaniemy z jednym punktem. Ten punkt jest najbliższy punktowi M. Całkowita operacja zajmuje kroki O (lgn).

W przypadku, gdy dane są pochylone i nierównomiernie rozmieszczone w kole, można optymalizować płaskie kawałki tak, że każde wycięcie przechodzi przez środkową (opartego na kącie) od tych punktów, które zostały pozostawione w operacji wyszukiwania.