Zadanie Przyjazne Punkty, obóz algorytmiczny Proserwy

Question

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/TVsad3dGJ7NrRODIkdxvDCOZ/site/?key=statement

Bruta O(N^2*lg(N)) umiem napisać, sortuję punkty po współrzędnej x, i z każdego zaczynam osobno, i czy da się połączyć punkt i-ty z innym mogę drzewem przedziałowym sobie odpowiedzieć łatwo.

Niestety mam problem co zrobić dalej.

Prosiłbym o jakiegoś hinta.

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

Mam pomysł w O(nlog^2n). Działa podobnie jak szukanie pary najbliższych punktów

Comments

zamiatanie z drzewem przedziałowym?

---

trochę więcej

---

A na cp algorithm jest opisane znajdywanie pary najbliższych punktów? Bo jeszcze się z tym algorytmem nie spotkałem nigdy.

---

tak

---

Nie rozumiem tego algorytmu. Dzielimy ala dziel i rządź na połówki, tylko czemu to działa?

---

Nie pamiętam dokładnie jak ten algorytm działa, ale algorytmy tego typu działają wtedy gdy umiemy szybko łączyć obydwie połówki. W tym przypadku robimy to liniowo, bo chyba bierzemy punkty, które oddalone są od lini podziału o nie więcej niż dotychczasowa minimalna odległość między punktami i potem sprytnie sprawdzamy czy te wybrane punkty nie są ze sobą jeszcze blizej