Omówienie zadania Ogrodzenie (III etap XXV OI)

Mamy \(n\) punktów na płaszczyźnie, z których każdy ma pewną wagę (wagi mogą być ujemne). Znaleźć wielokąt wypukły (którego wierzchołkami są niektóre punkty ze zbioru), taki że suma wag punktów zawartych w wielokącie jest największa możliwa.

Podzadanie 1

Będziemy chcieli przejrzeć wszystkie \(2^n\) podzbiorów punktów i znaleźć te, które odpowiadają podzbiorom punktów zawartych w pewnych wielokątach wypukłych.

Na początek wykonamy obliczenia wstępne, w których przeanalizujemy każdą trójkę punktów z wejścia; tych trójek mamy \(O(n^3)\). Dla każdej z nich zbudujemy trójkąt, a następnie dla każdego trójkąta policzymy maskę bitową kodującą podzbiór punktów zawartych w tym trójkącie. Jak sobie za chwilę pokażemy, tę część będziemy mogli wykonać w czasie \(O(n^4)\) i będzie to jedyny geometryczny kawałek implementacji tego rozwiązania.

Następnie przejrzymy wszystkie \(2^n\) podzbiorów punktów i dla każdego podzbioru przejrzymy \(O(n^3)\) trójkątów generowanych przez punkty tego podzbioru i wykonamy operację bitowy or dla wszystkich masek dla tych trójkątów. To spowoduje, że wyznaczymy maskę bitową punktów znajdujących się wewnątrz otoczki wypukłej i jeżeli ta maska będzie większa niż maska podzbioru, to wtedy wiemy, że podzbiór jest nieprawidłowy. Zauważmy, że o ile obliczenia wstępne \(O(n^4)\) dla \(n \leq 20\) spokojnie zmieszczą się w czasie, to złożoność \(O(2^n n^3)\) jest już trochę duża.

Możemy ją jednak stosunkowo łatwo zmniejszyć. Załóżmy, że mamy pewien podzbiór reprezentujący maskę bitową \(S = \{ A_1, \ldots, A_s \}\). Oczywiście rozważamy tylko zbiory, które mają co najmniej trzy wierzchołki, bo dla jednego lub dwóch wierzchołków nie utworzą one figury wypukłej o dodatnim polu. Jeżeli \(S\) ma dokładnie trzy wierzchołki, to wiemy, że jest trójkątem i wynik możemy bezpośrednio odczytać z obliczeń wstępnych. W przypadku podzbioru co najmniej czterech wierzchołków rozważamy teraz wszystkie \(S\) masek, które powstają poprzez usunięcie jednego z wierzchołków: \(S_i = S \setminus \{ A_i \}\).

Okazuje się, że suma otoczek wypukłych dla tych wszystkich mniejszych zbiorów jest równa otoczce wypukłej dla zbioru \(S\). Jest tak dlatego, że każdy trójkąt, który możemy utworzyć z wierzchołków zbioru \(S\), znajduje się w którymś z tych mniejszych podzbiorów. Jeśli bowiem \(A_i\) jest najmniejszym wierzchołkiem nienależącym do tego trójkąta, to ten trójkąt będzie można zbudować z wierzchołków z podzbioru \(S_i\). Jeżeli więc weźmiemy or wszystkich masek bitowych z tych mniejszych podzbiorów, to będzie to równoważne wzięciu or z wszystkich trójkątów generowanych przez te podzbiory. To w konsekwencji będzie or wszystkich trójkątów generowanych przez maskę \(S\), czyli będzie to zawierać wszystkie punkty należące do otoczki wypukłej \(S\).

To spowoduje, że czas działania naszego algorytmu zmniejszy się do \(O(2^n n)\), ponieważ dla każdego podzbioru wystarczy, że rozważymy \(O(n)\) mniejszych masek bitowych.

Tak naprawdę możemy pójść jeszcze dalej i rozważyć jedynie trzy podzbiory \(S_1\), \(S_2\) i \(S_3\), bo jedynym trójkątem, który nie będzie generowany przez te podzbiory, będzie trójkąt \(A_1 A_2 A_3\). Tak więc jeżeli weźmiemy or z tych trzech podzbiorów oraz dodatkowo z maski bitowej dla trójkąta \(A_1 A_2 A_3\), to znajdziemy maskę bitową dla otoczki wypukłej \(S\). Tym sposobem każdą maskę bitową przeanalizujemy w czasie stałym.

Wobec tego całe rozwiązanie będzie działało w czasie \(O(2^n + n^4)\).

Zliczanie punktów w trójkątach

Pokażemy teraz jak dla każdego trójkąta o wierzchołkach w punktach z wejścia znaleźć zbiór punktów, który jest w nim zawarty. Niezależnie dla każdego trójkąta \(A B C\) będziemy iterować się po wszystkich pozostałych punktach \(P\) i dla każdego punktu będziemy sprawdzać, czy należy on do trójkąta. Robimy to w czasie \(O(1)\), sprawdzając po której stronie prostych \(A B\), \(B C\) i \(C A\) znajduje się punkt \(P\). Do tego wystarczy wyznaczyć znak odpowiedniego iloczynu wektorowego, np. dla prostej \(A B\) będzie to \[A B \times A P = (x_B - x_A) (y_P - y_A) - (x_P - x_A)(y_B - y_A).\]

Wobec tego całe rozwiązanie będzie miało złożoność \(O(n^4)\). Analogiczną metodę możemy zastosować, żeby zamiast zbioru punktów znaleźć sumę wartości punktów znajdujących się wewnątrz trójkąta.

Warto wspomnieć też o tym, że ten algorytm nie jest najszybszy z możliwych, a mianowicie jesteśmy w stanie stablicować odpowiedzi dla wszystkich \(O(n^3)\) trójkątów w czasie \(O(n^3)\), a nawet w czasie \(O(n^2 \log n)\) zbudować strukturę danych, która będzie odpowiadać w czasie stałym na pytanie, jaka jest suma wartości punktów wewnątrz danego trójkąta. Zainteresowanych taką strukturą odsyłam do opisu zadania Poligon zamieszczonego w książce W poszukiwaniu wyzwań.

Pokrywanie wielokąta trójkątami i trapezami

Zanim przejdziemy do podzadania 2, pokażemy, w jaki sposób dla danego wielokąta wypukłego policzyć, jaka jest suma wartości punktów znajdujących się w jego wnętrzu i na jego brzegu.

Możemy w tym celu skorzystać z informacji, które obliczyliśmy dla trójkątów. W tym celu wyróżnimy sobie pewien wierzchołek \(P\) naszego wielokąta i przekątnymi łączącymi ten wierzchołek z pozostałymi podzielimy nasz wielokąt na trójkąty. Wystarczy teraz zsumować stabilizowane wartości dla wszystkich trójkątów oraz dodać wartości dla punktów leżących na brzegu wielokąta. Z założenia, że żadne trzy punkty nie leżą na jednej prostej, wiemy, że nie będziemy musieli się przejmować przypadkami szczególnymi, w których jakiś punkt leży na przekątnej.

Podział wielokąta na trójkąty, aby obliczać sumę wartości punktów w jego wnętrzu, nie jest jedynym rozwiązaniem. Pokażemy jeszcze podział na trapezy, który umożliwi nam szybszy preprocessing. Trapez będzie opisany punktami \(A\) i \(B\) (dla \(x_A < x_B\)) i będzie zawierał wszystkie punkty leżące na prawo od pionowej prostej przechodzącej przez punkt \(A\), leżące na lewo od pionowej prostej przechodzącej przez punkt \(B\) i leżącej poniżej prostej przechodzącej przez punkty \(A\) i \(B\). W szczególności taki trapez będzie nieograniczony z dołu.

Zauważmy, że mamy \(O(n^2)\) wszystkich trapezów i jeżeli preprocessing znowu wykonamy w całkiem naiwny sposób, dostaniemy całkowitą złożoność czasową równą \(O(n^3)\), Co jest szybsze niż nasz preprocessing dla trójkątów, który wykonywaliśmy w czasie \(O(n^4)\).

Jak podzielić wielokąt na takie nieograniczone z jednej strony trapezy? Na początek wyróżnimy w naszym wielokącie skrajnie lewy i skrajnie prawy wierzchołek. Podzielą one brzeg wielokąta na dwa kawałki: kawałek górny i kawałek dolny.

Teraz rozważymy wszystkie trapezy odpowiadające krawędziom należącym do górnej części brzegu i zsumujemy wartości punktów leżących we wszystkich tych trapezach. To oczywiście spowoduje, że posumujemy wszystkie punkty leżące we wnętrzu wielokąta, ale też niektóre punkty, które leżą poniżej jego wnętrza. Wobec tego w drugim kroku zbudujemy analogiczny zbiór trapezów dla dolnej części brzegu i od uzyskanego wyniku odejmiemy sumę punktów znajdujących się w ich wnętrzach. Co spowoduje, że ucinamy wkład z punktów leżących poniżej wielokąta, który wcześniej był uwzględniony w sumie.

Tym razem jednak będziemy musieli zwrócić uwagę na punkty, które będą mogły znajdować się na lewym lub prawym brzegu trapezu. Dla górnych trapezów możemy na przykład przyjąć, że zliczamy je włączając punkt \(A\) oraz wszystkie punkty leżące na lewej krawędzi. Natomiast nie zliczamy punktu \(B\) ani punktów leżących na prawej krawędzi.

Podzadanie 2

Jak to zwykle bywa w przypadku zadań optymalizacyjnych, warto rozważyć, czy dałoby się tutaj zastosować metodę programowania dynamicznego. O ile jednak dla zadań, które dzieją się na ciągu albo w dwuwymiarowej tablicy, znamy standardowe metody generowania podproblemów (na przykład może być to prefiks ciągu lub jakiś podprostokąt w tablicy), to w przypadku zadania geometrycznego, w którym mamy punkty na płaszczyźnie, nie bardzo widać, w jakim kierunku takie programowanie dynamiczne mogłoby iść.

Spróbujmy jednak wykorzystać to, co powiedzieliśmy przed chwilą o zliczaniu sumy wartości punktów wewnątrz wielokąta za pomocą podziału na trapezy, a konkretnie to, że mogliśmy tego dokonać wykonując dwa niezależne obliczenia, jeden dla górnej części wielokąta, a drugi dla dolnej części. Zauważmy, że współrzędne \(x\) wierzchołków zarówno w górnej, jak i w dolnej części będą uporządkowane rosnąco. Sugeruje to, że moglibyśmy spróbować skonstruować taką górną i dolną część, przeglądając wierzchołki właśnie w takiej kolejności.

Dla dwóch ustalonych punktów \(A\) i \(B\) będziemy chcieli znaleźć optymalny górny brzeg, który zaczyna się w lewym punkcie \(A\) i kończy w prawym punkcie \(B\) i przechodzi przez jakieś punkty pośrednie; brzeg ten jest wypukły do góry oraz suma wartości wszystkich punktów leżących w trapezach wyznaczonych przez krawędzie z tego brzegu jest maksymalna możliwa.

Analogicznie będziemy chcieli znaleźć optymalny dolny brzeg pomiędzy punktami \(A\) i \(B\). Teraz będzie on wypukły w dół oraz suma wartości wszystkich punktów dla trapezów zbudowanych z krawędzi tego brzegu będzie minimalna możliwa.

Pokażemy teraz konstrukcję górnej części brzegu, konstrukcja dolnej części jest analogiczna. Najprostszym kandydatem na brzeg pomiędzy tymi dwoma punktami jest oczywiście brzeg zawierający tylko jeden odcinek \(AB\); będzie on zawierał wszystkie punkty leżące w trapezie \(AB\).

Załóżmy więc zatem, że mamy jakiś punkt wewnętrzny na brzegu. Możemy przeiterować się po wszystkich punktach leżących pomiędzy punktami \(A\) i \(B\) w poszukiwaniu przedostatniego punktu na tym brzegu. Jeżeli ustalimy sobie taki punkt \(P\), to wiemy, że wkład do brzegu będzie miał trapez \(PB\), a poza tym będziemy chcieli znaleźć optymalną część brzegu łączącą punkty \(A\) oraz \(P\). Niestety ten brzeg nie może być zupełnie dowolny ponieważ musimy jeszcze kontrolować kąt, jaki utworzą krawędzie w wierzchołku \(P\), nie możemy bowiem popsuć wypukłości.

Tak więc będziemy tutaj potrzebowali dodatkowej informacji o naszym brzegu, żebyśmy wiedzieli, jakie jest nachylenie jego ostatniej krawędzi. W tym celu w podproblemach będziemy pamiętali jeszcze, jaki jest przedostatni punkt na górnym brzegu. Dzięki temu znając przedostatni punkt \(Q\) oraz ostatni punkt \(P\) mniejszego brzegu oraz ostatni punkt na całym brzegu \(B\), będziemy w stanie wyznaczyć kąt w wierzchołku \(P\) i uwzględniać tylko te mniejsze brzegi, dla których ten kąt jest wypukły.

Będziemy więc wypełniać trójwymiarową tabelkę \(dp\) indeksowaną trzema punktami \(A\), \(P\) oraz \(B\). W komórce \(dp[A,P,B]\) zapamiętamy maksymalną wartość punktów, które leżą pod górnym brzegiem zaczynającym się w punkcie \(A\), kończącym się w punkcie \(B\) i mającym punkt \(P\) jako przedostatni punkt. Żeby wyznaczyć tę wartość, bierzemy teraz maksimum po wszystkich punktach \(Q\) z mniejszego brzegu, który zaczyna się w punkcie \(A\), kończy w punkcie \(P\), ma punkt \(Q\) jako przedostatni (czyli wartość \(dp[A,Q,P]\)), plus wartość punktów w trapezie \(PB\); przy czym kąt utworzony przez punkty \(QPB\) musi mieć mniej niż \(180^\circ\):

\[dp[A,P,B] = \max_{\textrm{dobre}\ P}\ dp[A,Q,P] + trap[P,B].\]

Musimy też zadbać o jakieś warunki początkowe rekurencji, na przykład takie, że jeżeli punktem przedostatnim jest punkt \(A\), to wtedy wiemy, że mamy dokładnie dwa punkty na brzegu, więc \(dp[A,A,B] = trap[A,B]\).

Nasza tabelka ma \(O(n^3)\) komórek i obliczanie każdej z komórek zajmuje nam czas liniowy, wobec tego całkowity czas wypełniania tabelki to jest \(O(n^4)\).

Teraz możemy wypełnić dwuwymiarową tabelkę, której tak naprawdę potrzebowaliśmy, to znaczy optymalną wartość dla górnego brzegu pomiędzy punktami \(A\) i \(B\): \[dp'[A,B] = \max_{P}\ dp[A,P,B].\]

Jeżeli wypełnimy też analogiczną tabelkę \(dp''\) zawierającą minima zdolnych brzegów, to do uzyskania odpowiedzi wystarczy wziąć \[\max_{A,B} dp'[A,B] - dp''[A,B].\]

Musimy dodać do tego jeszcze początkowe obliczanie tabelki dla trapezów, które jak powiedzieliśmy działa w czasie \(O(n^3)\). Ostatecznie całkowita złożoność rozwiązania to \(O(n^4)\).

Podzadanie 3

W aktualnym rozwiązaniu złożoność czasową dość mocno podbija kontrolowanie wypukłości wielokąta, bo trzymamy zarówno punkt \(P\), jak i punkt \(Q\), co pozwala nam dokładnie obliczać wielkość tworzonego kąta. Zauważmy jednak, że nie musimy dokładnie znać wielkości tego kąta, wystarczy tylko, żeby był mniejszy niż \(180^\circ\).

Pomysł jest następujący: podproblem będziemy opisywali punktami \(A\) i \(B\) oraz prostą przechodzącą przez punkt \(B\). Prostą taką będziemy reprezentowali za pomocą drugiego punktu \(C\), który przez nią przechodzi, więc tabelka oprogramowania dynamicznego nadal będzie miała trzy wymiary \(dp[A,B,C]\). Teraz będziemy w takiej komórce pamiętać optymalny górny brzeg, który zaczyna się w punkcie \(A\), kończy w punkcie \(B\) oraz żaden z jego kawałków nie leży nad prostą \(CB\) (wobec tego prawidłowym będzie brzeg zawierający odcinek \(CB\), ale również brzeg, który w całości będzie znajdował się pod prostą \(CB\)).

Proste wokół punktu \(B\) będziemy trzymać posortowane przeciwnie do ruchu wskazówek zegara. Przy czym należy zwrócić uwagę, że nie jest to po prostu posortowanie punktów wokół punktu \(B\), ale całych prostych niezależnie od tego, po której stronie takiej prostej znajduje się wyznaczający ją punkt. Dzięki tej sztuczce w rekurencji będziemy musieli wziąć maksimum jedynie z dwóch przypadków, a nie liniowej ich liczby.

Pierwszy przypadek jest taki, że górny brzeg dla punktów \(A\), \(B\), \(C\) zawiera odcinek \(CB\). Tak więc będzie zawierał wszystkie punkty z trapezu \(CB\) oraz optymalny górny brzeg między punktami \(A\) oraz \(C\), z tym, że ten brzeg nadal będzie musiał się zawierać pod prostą \(CB\). Zauważmy, że ta prosta z perspektywy punktu \(C\) jest wyznaczona przez punkt \(B\).

Drugi przypadek mamy wtedy, kiedy górny brzeg dla punktów \(A\), \(B\) i \(C\) nie zawiera krawędzi \(BC\). Wtedy musi znajdować się ściśle pod prostą \(BC\), to znaczy, że możemy delikatnie obrócić tę prostą i nadal będzie ona co najwyżej dotykała do tego brzegu. Możemy ją obrócić, aż stanie się ona następną w kolejności prostą wokół punktu \(B\). Podczas sortowania prostych, dla każdego punktu wyznaczającego prostą \(C\), zapiszemy sobie w tablicy \(next[C]\) punkt wyznaczający następną prostą w kolejności.

Ostatecznie wzór rekurencyjny przyjmie postać \[dp[A,B,C] = \max( trap[C,B] + dp[A,C,B],\ dp[A,B,next[C]] ).\]

Warto zwrócić uwagę na kolejność, w jakiej musimy wypełniać tę tabelkę, a mianowicie punkty \(C\) będziemy musieli wypełniać w kolejności posortowanych prostych. Tabelkę \(dp'[A,B]\) oraz dalsze obliczenia wykonujemy tak jak poprzednio.

Ostatecznie całkowita złożoność rozwiązania to \(O(n^3)\).