Zadanie Przyjazne Punkty, obóz algorytmiczny Proserwy

pytanie zadane 9 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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!

1 odpowiedź

odpowiedź 9 maja 2023 przez Whistleroosh Maniak (57,360 p.)

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

komentarz 9 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

zamiatanie z drzewem przedziałowym?

komentarz 9 maja 2023 przez Whistleroosh Maniak (57,360 p.)

trochę więcej

komentarz 9 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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

komentarz 9 maja 2023 przez Whistleroosh Maniak (57,360 p.)

tak

komentarz 14 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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

komentarz 14 maja 2023 przez Whistleroosh Maniak (57,360 p.)

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