Omówienie zadania Tort (III etap XXX OI)

Zadanie

Dany jest wielokąt o \(n \leq 300\,000\) bokach równoległych do osi współrzędnych i którego wierzchołki mają współrzędne całkowite z zakresu \([1, 10^6 - 1]\). Chcemy narysować \(k \leq 300\,000\) prostych przechodzących przez \((0, 0)\), które podzielą wielokąt na \(k + 1\) obszarów o równych polach. Rozwiązanie musimy wypisać z dokładnością do \(d\) miejsc po przecinku w zapisie dziesiętnym (tutaj: \(d=6\)).

Rozwiązanie do podzadania \(n=4, k = 1\) (w ogólności niepoprawne)

Skoro boki wielokąta są równoległe do osi oraz ma on cztery wierzchołki, to jest to prostokąt. Zauważmy, że każda prosta przechodząca przez środek prostokąta dzieli go na dwie figury o równych polach powierzchni. Zatem w tym podzadaniu szukanym cięciem jest prosta przechodząca przez środek prostokąta i początek układu współrzędnych. Wystarczy, że wypiszemy współrzędne środka prostokąta.

Rozwiązanie wolne \(O(nkd)\)

Ważne w zadaniu jest wykorzystanie formatu, w jakim są nam zadane wierzchołki wielokąta. Są to koordynaty \(x, y\) kolejnych jego wierzchołków w kolejności obchodzenia wzdłuż brzegu. Dla tak zadanego wielokąta \((x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\) jesteśmy w stanie w czasie \(O(n)\) obliczyć jego pole powierzchni, posługując się jednym z prostych wzorów matematycznych (dla wygody zakładamy \((x_{n+1}, y_{n+1}) = (x_1, y_1)\)):

• metoda trapezów: dla każdego boku wielokąta obliczamy pole trapezu prostokątnego pod nim, ograniczonego od dołu osią OX. Dodajemy to pole do wyniku z odpowiednim znakiem, który zależy tylko od orientacji tego boku. Wyraża się to następującym wzorem:
  \[ S = \left|\frac12 \sum_{i=1}^n (y_i + y_{i + 1})(x_i - x_{i+1})\right| \]
  W przypadku tego zadania trapezy wyznaczone przez boki pionowe będą sie wliczać do tej sumy jako zero, przez boki poziome idące z lewa na prawo - negatywnie, a przez takie z prawa na lewo - pozytywnie (lub z przeciwnymi znakami w zależności od tego, czy obchodzimy wielokąt zgodnie z ruchem wskazówek zegara, czy do niego przeciwnie). W ten sposób składniki sumy reprezentujące pola spoza wielokąta, anulują się wzajemnie.
• metoda trójkątów: postępujemy podobnie jak powyżej, ale zamiast trapezów rozważamy trójkąty \(AOB\), gdzie \(A, B\) to końce danego boku wielokąta, a \(O\) to środek układu współrzędnych. Wzór w tym przypadku jest następujący:
  \[ S = \left| \frac12 \sum_{i=1}^n (x_i y_{i+1} - x_{i+1} y_i) \right| \]
• inne, równoważne wzory, np. \(\frac12 \sum_{i=1}^n x_i(y_{i+1}-y_i)\). Więcej na ten temat można doczytać w artykule na angielskiej Wikipedii: https://en.wikipedia.org/wiki/Shoelace_formula.

W tym opisie pokażemy rozwiązanie oparte o metodę trójkątów.

Niech \(S\) będzie polem wielokąta na wejściu w zadaniu. Rozwiążemy oddzielnie dla każdego \(i \in \{1, \dots, k\}\) następujący problem: znajdź kąt \(\alpha_i \in (0, 90^\circ)\) taki, że jeśli pokierować prostą przechodzącą przez \((0, 0)\) pod kątem \(\alpha_i\) względem osi OX, to od dołu odetnie ona pole \(\frac{i}{k + 1} \cdot S\) od naszego wielokąta. Wówczas znalezienie odpowiedzi będzie proste: dla każdego \(i\) podamy punkt \((\cos(\alpha_i), \sin(\alpha_i))\).

Musimy jeszcze omówić w jaki sposób obliczyć tę część pola wielokąta, która leży poniżej prostej \(OP\) dla danego punktu \(P\). W tym celu posłużymy się wzorem zapisanym powyżej i jego interpretacją opartą o dodawanie/odejmowanie pól trójkątów \(\triangle AOB\). Możemy dla każdego takiego trójkąta z osobna obliczyć jego pole leżące poniżej tej prostej i zsumować identycznie jak powyżej. Wymaga to rozpatrzenia przypadków w zależności od orientacji odcinka \(AB\).

• Załóżmy wpierw, że odcinek \(AB\) jest pionowy i łączy punkty \((x_0, y_1)\), \((x_0, y_2)\), gdzie \(y_1 < y_2\). Niech \(y_0 := x_0 t\) będzie wysokością, na której prosta \(OP\) przecina się z prostą o równaniu \(x = x_0\) (tj. zawierającą odcinek \(AB\)). Zauważmy, że \(t\) jest tangensem kąta nachylenia prostej \(OP\) względem osi OX (to będzie nam potrzebne później). Mamy trzy przypadki:
  • Odcinek \(AB\) znajduje się w całości nad prostą \(OP\) (tj. gdy \(y_0 \leq y_1\)). Wtedy odcinek ten nie wpływa na wartość powyższej sumy.
  • Odcinek \(AB\) znajduje się w całości pod prostą \(OP\) (tj. gdy \(y_0 \geq y_2\)). Wtedy wkład odcinka na wartość sumy jest równy polu trójkąta \(AOB\) z odpowiednim znakiem; składnik ten jest niezależny od \(t\).
  • Odcinek \(AB\) przecina prostą \(OP\) (gdy \(y_1 < y_0 < y_2\)). Niech \(X := (x_0, y_0)\) będzie punktem przecięcia. Wtedy nietrudno obliczyć, że wkład do sumy składnika odpowiadającego odcinkowi \(AB\) wynosi plus / minus \[ \frac{1}{2} (y_0 - y_1) x_0 = \frac{1}{2} \left( x_0^2 t - y_1x_0 \right). \] Wkład odcinka zależy więc liniowo od \(t\).
• Przypuśćmy teraz, że odcinek \(AB\) jest poziomy i łączy punkty \((x_1, y_0)\), \((x_2, y_0)\), gdzie \(x_1 < x_2\). Niech \(x_0 := y_0 / t\) będzie szerokością, na której prosta \(OP\) przecina się z prostą zawierającą odcinek \(AB\). Zauważmy że ponownie \(t = y_0 / x_0\) jest tangensem nachylenia \(OP\). Podobnie jak poprzednio mamy trzy przypadki: odcinek \(AB\) nie liczy się do sumy w ogóle, liczy się w całości lub liczy się częściowo. Dwa pierwsze przypadki ponownie są proste. Rozpatrzmy więc trzeci. Zakładamy, że \(x_1 < x_0 < x_2\). Obliczamy, że wkład do sumy składnika odpowiadającego odcinkowi \(AB\) wynosi plus/minus \[ \frac{1}{2} (x_2 - x_0) y_0 = \frac{1}{2} \left( x_2y_0 - \frac{y_0^2}{t} \right). \] Wkład odcinka zależy więc liniowo od \(\frac{1}{t}\).

Dla każdego \(i\) rozwiązujemy zadanie wyszukiwaniem binarnym po wyniku \(\alpha_i\). Dla każdego kąta \(\beta\) testowanego w danej iteracji wyszukiwania binarnego sprawdzamy w czasie \(O(n)\), jaka część pola wielokąta znajduje się poniżej prostej przechodzącej przez \((0, 0)\) pod kątem \(\beta\) względem osi OX. Ostatecznie, skoro zadanie wymaga od nas wypisania sinusa/cosinusa kąta \(\beta\) z dokładnością rzędu \(10^{-d}\), to dla każdego kąta \(\alpha_i\), musimy wykonać ok. \(d' = \log_2(10^d) = d \log_2(10) = O(d)\) iteracji przybliżania wyniku. Musimy tutaj rozróżnić dokładność, z jaką przybliżamy kąt \(\alpha_i\) od dokładności, z jaką wypiszemy \(\sin(\alpha_i)\). Możemy jednak założyć, że zagwarantowanie odpowiedniej dokładności sinusa / cosinusa nie będzie wymagało od nas dużo większej dokładności kąta. W praktyce powinna wystarczyć jedna dodatkowa iteracja wyszukiwania binarnego.

W każdej z \(O(d)\) iteracji musimy obliczać pole pewnego wielokąta, co robimy za każdym razem w czasie \(O(n)\). Musimy tak przybliżyć \(k\) kątów, co daje złożoność \(O(k \cdot n \cdot d)\)

Rozwiązanie wzorcowe 1: \(O(n \log n + kd)\)

Po pierwsze, zamiast kąta \(\alpha_i \in (0, \frac{\pi}{2})\) znajdziemy jego tangens \(t_i := \mathrm{tg}\,\alpha_i \). Z uwagi na ograniczenia na wartość \(x\) i \(y\) w zadaniu na pewno zachodzić będzie nierówność \(t_i \leq 10^7\). Proste rachunki trygonometryczne pokazują, że

Zaprezentujemy rozwiązanie oparte na technice zamiatania. Będziemy zamiatać wielokąt kątowo prostą przechodzącą przez \((0, 0)\), zaczynając od kąta \(0\) względem osi OX i kończąc na kącie \(\pi / 2\). Tę prostą będziemy od tej pory nazywać zwyczajowo miotłą.

W trakcie zamiatania każdy odcinek jest w jednym z trzech stanów: albo jest w całości nad miotłą, albo przecina miotłę, albo jest w całości pod miotłą. Na początku wszystkie odcinki są w całości nad miotłą; miotła reaguje na zmiany postaci „odcinek nad miotłą \(\to\) odcinek przecina miotłę” i „odcinek przecina miotłę \(\to\) odcinek pod miotłą”. Takich zmian (zdarzeń) będzie dokładnie \(2n\). Oznaczmy teraz \(t = \mathrm{tg}\,\beta\). Przypuśćmy, że wiemy już, że szukane aktualnie \(t\) znajduje się w przedziale od ostatniego zdarzenia do następnego zdarzenia. Przypomnijmy, że przy omówieniu wzoru na pole wielokąta, zwróciliśmy uwagę na to, że wkład każdego boku do pola jest albo stały, albo zależny liniowo od \(t\), albo liniowo od \(\frac{1}{t}\). Nietrudno zauważyć, że pomiędzy każdymi dwoma zdarzeniami na miotle, część pola znajdującego się pod miotłą jest równa dokładnie \[ \frac{1}{2} \left( At + B + \frac{C}{t} \right), \] dla pewnych liczb całkowitych \(A\), \(B\), \(C\), które możemy utrzymywać podczas zamiatania i które zmieniają się tylko podczas przetwarzania zdarzeń na miotle.

W trakcie zamiatania musimy znajdować wartości \(t\), dla których pole \(\frac{1}{2} \left( At + B + \frac{C}{t} \right)\) jest równe kolejno \(\frac{1}{k+1} \cdot S\), \(\frac{2}{k+1} \cdot S\), \(\dots\), \(\frac{k}{k+1} \cdot S\). Możemy to zrobić w następujący sposób: pamiętamy, ile cięć już zrobiliśmy (\(\ell\)), i sprawdzamy, czy do następnego zdarzenia na miotle przekroczymy pole \(\frac{\ell+1}{k+1} \cdot S\). Jeśli tak się stanie, wykonujemy wyszukiwanie binarne po wartości \(t\) (na przedziale od ostatniego do następnego zdarzenia) w poszukiwaniu wartości \(t\), dla której \(\frac{1}{2} \left( At + B + \frac{C}{t} \right) = \frac{\ell+1}{k+1} \cdot S\). Znając wystarczająco dokładną wartość \(t\), obliczamy odpowiednie wartości sinusa i cosinusa, posługując się transformacją z początku tej sekcji. Wypisujemy je i kontynuujemy wyszukiwanie dla wartości \(\ell\) powiększonej o \(1\).

Jeśli wszystko zaimplementujemy poprawnie, otrzymamy rozwiązanie w złożoności \(O(n \log n + kd)\). Lekko niedbała implementacja działa w złożoności \(O((n + k) (\log n + d))\), jednak także pozwala uzyskać komplet punktów.

Rozwiązanie wzorcowe 2: \(O(k + n \log n)\)

To mała zmiana do rozwiązania wzorcowego powyżej, która pozbywa się wyszukiwania binarnego po wyniku \(t\).

Przypuśćmy, że wiemy już, że szukane \(t\) znajduje się w przedziale od ostatniego zdarzenia do następnego zdarzenia. W tej sytuacji rozwiązujemy równanie

gdzie \(X = \frac{\ell+1}{k+1} \cdot S\) jest liczbą wymierną, a \(A\), \(B\), \(C\) są liczbami całkowitymi o wartości bezwzględnej nieprzekraczającej \(n \cdot (10^6)^2 \leq 3 \cdot 10^{17}\). Zauważmy jednak, że ponieważ szukamy \(t > 0\), to powyższe równanie jest równoważne następującemu: \[ At^2 + (B - 2X)t + C = 0, \] które jest równaniem kwadratowym. Skoro wiemy, że oryginalne równanie miało przynajmniej jedno rozwiązanie w rozważanym przedziale, to nowe również musi je mieć. Możemy je znaleźć za pomocą znanego wzoru na pierwiastki trójmianów kwadratowych. Trzeba koniecznie pamiętać o tym, że może się zdarzyć sytuacja, w której \(A = 0\). Wtedy wzór na rozwiązania równania kwadratowego nie jest poprawny i równanie trzeba potraktować jako równanie liniowe. Ponieważ jednak równanie ma dokładnie jedno rozwiązanie, to zadane równanie liniowe na pewno nie jest zdegenerowane, tj. w tym przypadku \(B - 2X \neq 0\). W ten sposób zbijamy złożoność do \(O(k + n \log n)\).