Omówienie zadania Zliczanie Z (III etap XXXIII OI)

Wstęp

W zadaniu dane są współrzędne \(n\) parami różnych punktów na płaszczyźnie. Dla uporządkowanej czwórki \((A, B, C, D)\) mówimy, że tworzy ona literę \(Z\), jeśli zachodzi \(0^\circ < \angle ABC = \angle DCB < 90^\circ\), gdzie \(\angle ABC\) oznacza miarę kąta utworzonego przez punkty \(A, B, C\) liczony przeciwnie do ruchu wskazówek zegara. Można więc myśleć o literze \(Z\) jako o dwóch równoległych odcinkach \(AB\) i \(DC\) połączonych „środkowym” odcinkiem \(BC\), do którego przylegają dwa równe, ostre kąty. Naszym zadaniem jest zliczenie wszystkich takich czwórek.

Rozwiązanie w czasie \(O(n^3)\)

Pierwszy krok to zdecydować, po jakim obiekcie będziemy się iterować. Naturalnym kandydatem jest „środkowy” odcinek litery \(Z\), czyli para \((B, C)\). Dla ustalonego \(BC\) jest on wspólnym ramieniem kątów \(\angle ABC\) i \(\angle DCB\), więc litera \(Z\) powstaje już tylko z „dobrania” końców: punktu \(A\) przy \(B\) i punktu \(D\) przy \(C\) tak, by oba kąty były ostre i równe.

Aby łatwiej odnaleźć odpowiednie pary punktów, uporządkujemy cały „widok” z każdego wierzchołka. Wokół każdego punktu sortujemy kątowo wszystkie wychodzące odcinki, normalizujemy je (dzieląc przez największy wspólny dzielnik współrzędnych wektora odpowiadającego odcinkowi) i dzielimy na kubełki z tym samym kierunkiem. Dla danego wierzchołka wystarczy nam lista kierunków i przypisana do każdego z nich liczba punktów. Dla ustalonego \(BC\) wybierzmy teraz dowolny znormalizowany kierunek wychodzący z \(B\) i nazwijmy jego wektor \(v\). Kierunek z \(C\), który może być z nim połączony w literę \(Z\), musi mieć wektor dokładnie przeciwny, \(-v\). Właśnie wtedy odcinki wychodzące z \(B\) i \(C\) są równoległe i mogą stać się ramionami dwóch równych kątów przy \(B\) i \(C\).

Żeby dodatkowo wymusić, by były ostre, sprawdzamy znak iloczynu wektorowego oraz dodatniość iloczynu skalarnego dla wektorów \(\overrightarrow{BA}\) i \(\overrightarrow{BC}\) (dzięki czemu nie musimy korzystać z funkcji trygonometrycznych ani typów zmiennoprzecinkowych). Dla danego \(BC\) liczymy więc pary \((A, D)\) wykorzystując technikę dwóch wskaźników po posortowanych listach. Pozwala to w jednym przejściu zliczyć wszystkie kombinacje spełniające ostre nierówności, a powtarzając ten proces dla wszystkich par \((B, C)\) otrzymujemy rozwiązanie o złożoności \(O(n^3)\).

Rozwiązanie w czasie \(O(n^2 \log n)\)

Rozwiązanie \(O(n^3)\) wykorzystuje fakt, że „środkowy” odcinek dobrze opisuje pojedynczą literę \(Z\), ale liczba takich odcinków jest zbyt duża. W wersji optymalnej zmieniamy więc punkt widzenia: iterujemy się nie po środkach, lecz po kierunkach ramion litery \(Z\). Dla wszystkich par punktów tworzymy odcinki je łączące, sortujemy je po nachyleniu i w każdej grupie równoległych odcinków pracujemy osobno.

W pojedynczej grupie chcemy obrócić wszystkie odcinki tak, by patrzeć na nie jak na poziome segmenty. Robimy to przez liniową transformację współrzędnych odpowiadającą obrotowi płaszczyzny: czysty obrót o kąt \(\varphi\) opisuje wzór \[(x', y') = (x\cos\varphi - y\sin\varphi,\; x\sin\varphi + y\cos\varphi).\] W naszym rozwiązaniu wybieramy \(\varphi\) tak, by kierunek rozważanych odcinków obrócić dokładnie na oś \(OX\); w implementacji nie liczymy jednak jawnie \(\cos\varphi\) i \(\sin\varphi\). Zamiast tego korzystamy bezpośrednio z wektora kierunkowego odcinka (jego współrzędnych \((a, b)\)) i traktujemy je jak „nieznormalizowane” \(\cos\varphi\) i \(\sin\varphi\). Ważne jest, by dla wszystkich punktów w jednej grupie równoległych odcinków używać tych samych \(a\) i \(b\) – tylko wtedy zachowujemy między nimi poprawną kolejność po obrocie. W praktyce sprowadza się to do bardzo prostego wzoru \[(x', y') = (ax - by,\; bx + ay),\] który jest dokładnie tym, co pojawia się w rozwiązaniu wzorcowym, aby nie korzystać z typów zmiennoprzecinkowych. W nowym układzie każdy odcinek to poziomy przedział \([x'_L, x'_R]\) na wysokości \(y'\). Dwa takie odcinki tworzą literę \(Z\) dokładnie wtedy, gdy znajdują się one na różnych wysokościach, a prawy koniec wyższego ma ściśle większe \(x'\) niż lewy koniec niższego.

Na tym etapie ważna jest już tylko kolejność, a nie konkretne współrzędne, więc kompresujemy \(y'\) do liczb z przedziału \([1, K]\), gdzie \(K\) oznacza liczbę różnych wartości \(y'\) (wysokości poziomych odcinków) pojawiających się w danej grupie. Teraz możemy przeprowadzić zamiatanie po \(x'\): każde zdarzenie „lewego końca” odcinka na wysokości \(y'\) dodaje \(1\) w drzewie przedziałowym na pozycji \(y'\), natomiast zdarzenie „prawego końca” odczytuje z drzewa sumę na przedziale \([1, y'-1]\). Jest to dokładnie liczba niższych odcinków, które da się połączyć z bieżącym w literę \(Z\). Po przetworzeniu grupy odcinków zerujemy drzewo i przechodzimy do kolejnego nachylenia.

Łącznie mamy \(O(n^2)\) odcinków, a każdą aktualizację i zapytanie w drzewie przedziałowym wykonujemy w czasie \(O(\log n)\), co razem ze skalowaniem współrzędnych daje złożoność \(O(n^2 \log n)\).