Drogi

Oznaczenia

Dla dwóch punktów $P_1=(x_1,y_1),P_2=(x_2,y_2)$, niech relacja mniejszości ($<$) będzie zdefiniowana jako $P_1<P_2⟺x_1<x_2\vee (x_1=x_2\wedge y_1<y_2)$. Intuicyjnie oznacza to, że punkt $P_1$ jest „na lewo” od punktu $P_2$ (z pewnym sposobem zdefiniowania remisów -- jeżeli punkty mają taką samą współrzędną $x$, to $P_1<P_2$ wtedy, gdy $P_1$ jest pod punktem $P_2$). Potocznie więc będziemy używać pojęcia „$P_1$ jest na lewo od $P_2$”, które oznacza, że $P_1<P_2$. W celu skrócenia implementacji rozwiązań warto pamiętać, że w języku C++ (i często też w innych językach) dokładnie tak jest zdefiniowana relacja $<$ (operator<) dla pair<int,int>, którym można reprezentować punkty z wejścia.

Początkiem odcinka $S=(P_1,P_2)$ niech będzie punkt bardziej na lewo z tych dwóch, a końcem ten bardziej na prawo.

Podzadanie 1

W przypadku, gdy wszystkie odcinki leżą na jednej prostej, jedynym rozwiązaniem jest połączyć każde sąsiednie dwa odcinki.

W ogólniejszym przypadku, gdzie wszystkie odcinki są pionowe, jednym z poprawnych rozwiązań jest połączyć w grupy w powyższy sposób wszystkie odcinki o tych samych współrzędnych $x$, a następnie dla każdych dwóch sąsiednich grup połączyć koniec ostatniego odcinka lewej grupy z początkiem pierwszego odcinka prawej grupy.

Zauważmy, że można to zaimplementować po prostu sortując odcinki po ich początkach według relacji $<$, a następnie łącząc koniec i początek każdych dwóch sąsiednich odcinków!

Podzadanie 2

Przy warunku, że każda para odcinków jest równoległa, powyższe rozwiązanie nadal działa, jednak trzeba inaczej posortować odcinki (tak, aby nadal były według relacji „jest na lewo”). Parę odcinków $S_1=(P_{1,1},P_{1,2})$ oraz $S_2=(P_{2,1},P_{2,2})$ można porównać za pomocą iloczynu wektorowego, odczytując znak wyrażenia $(P_{2,1}-P_{1,2})\times (P_{1,2}-P_{1,1})$ (jeżeli to wyrażenie wynosi $0$, można posortować początki według relacji $<$).

Pełne rozwiązanie

Powyższe podejście sugeruje \textit{zamiatanie} -- rozpatrzenie punktów w określonej kolejności, aby skorzystać z własności relacji i sposobu podzielenia punktów na „już rozpatrzone” oraz „jeszcze nie rozpatrzone”, dzięki czemu można utrzymywać odpowiednią strukturę danych do obliczenia wyniku (potencjalnie prostszą, niż przy innych podejściach).

Rozpatrzmy więc wszystkie punkty (zarówno początki odcinków, jak i ich końce, pamiętając przy okazji do których odcinków należą) w kolejności relacji $<$.

Nazwa \textit{zamiatanie} nawiązuje do sposobu wizualizacji działania algorytmu. Rozpatrując dany punkt $P$, pozostałe punkty można podzielić na takie, które są „na lewo” od miotły (pionowej prostej przechodzącej przez punkt $P$) oraz „na prawo”. Miotła porusza się w prawo wraz z rozpatrzeniem kolejnych punktów i „zamiata” punkty, zmieniając ich stan.

W tym zadaniu konkretniej mamy do czynienia z odcinkami, więc każdy taki odcinek może mieć stan „aktualny” (przecinający się z miotłą), „rozpatrzony” (na lewo od miotły) oraz „jeszcze nie rozpatrzony” (na prawo od miotły), przy czym ostatni stan oznacza punkt / odcinek jeszcze nie mający wpływu na wypisane rozwiązanie, więc go pomijamy w przykładach.

W momencie, gdy odcinek zmienia swój stan na aktualny, będzie on przypinany nowym odcinkiem do aktualnych/rozpatrzonych odcinków. Kluczem jest znalezienie jakiegoś takiego rozpatrzonego punktu, aby nowo dodany odcinek nie przecinał się z żadnym innym.

Strategia przypinania punktu do najbardziej prawego rozpatrzonego punktu by działała, gdyby tylko nie obecność aktywnych odcinków, przez które nowo powstały odcinek mógłby mieć przecięcia. Dobrym pomysłem jest więc rozpatrywanie punktów tylko pomiędzy aktywnym odcinkiem tuż nad oraz tuż pod rozpatrywanym punktem (gdzie „pomiędzy” jeszcze nie jest formalnie zdefiniowane) i z nich wybranie najbardziej prawego punktu.

We wzorcowym rozwiązaniu utrzymywany jest uporządkowany zbiór aktywnych odcinków (w kolejności od „dołu” do „góry”). Można to wykonać korzystając z set z własnym komparatorem -- kontener utrzymuje indeksy odcinków, a komparator porównuje dwa odcinki porównując współrzędne $y$ ich przecięcia z miotłą (aby uniknąć błędy precyzji, warto spróbować wykonywać obliczeń na liczbach całkowitych) lub alternatywnie porównując za pomocą iloczynu wektorowego. Tak zdefiniowany porządek ma sens -- odcinki tworzą porządek liniowy za każdym razem, gdy kontener jest modyfikowany (pomimo tego, że niektóre pary odcinków są nieporównywalne według tej definicji) oraz dwa odcinki zawsze są w tej samej relacji między sobą.

Można dzięki temu wykonać część operacji potrzebnych w rozwiązaniu wzorcowym -- dodanie i usunięcie aktywnego odcinka oraz zapytanie się o pierwszy odcinek „od góry” względem danego punktu na miotle (na przykład korzystając z set.lower_bound). Dla wygody implementacji, żeby taki „pierwszy odcinek” zawsze istniał, można na początku algorytmu dodać sztuczny odcinek o wystarczającej szerokości będący nad wszystkimi odcinkami.

Została więc kwestia szukania punktu najbardziej na prawo wśród punktów między dwoma aktywnymi odcinkami. Aby to zrobić, można zdefiniować obszar między aktywnymi odcinkami jako zbiór wszystkich punktów na prawo od początków tych dwóch odcinków, na lewo od miotły, pod górnym aktywnym odcinkiem oraz (o ile istnieje) nad dolnym aktywnym odcinkiem (tak jak ja rysunku). Jeżeli nie ma żadnego odcinka w tym obszarze, najbardziej prawym punktem może być jeden z początków aktywnych odcinków.

Tablicę rightmost_under[i] dla danego aktywnego odcinka $i$ można utrzymywać w następujący sposób -- gdy odcinek $i$ właśnie staje się aktywny, to wartość w komórce w tej tablicy oraz wartość odcinka nad $i$-tym odcinkiem można przypisać na początek $i$-tego odcinka. Analogicznie, gdy odcinek $i$ przestaje być aktywny, to odcinkowi nad $i$-tym wystarczy ustawić wartość na koniec $i$-tego odcinka (a wartość dla $i$-tego odcinka nie będzie już używana). Widać więc, że z każdym kolejnym rozpatrywanym punktem, co najwyżej dwie wartości tablicy rightmost_under zostaną zmienione w czasie $O(1)$.

Algorytm się sprowadza do zamiatania, utrzymywania set-a oraz tablicy rightmost_under i łączenia nowego aktywnego odcinka z rightmost_under[odcinek nad rozpatrywanym]. Działa więc w złożoności $O(n\log n)$ przez sortowanie punktów (dla zamiatania) oraz wykonywania liniowej ilości operacji na kontenerze set.

Podzadanie 3

Gdy każdy odcinek jest pionowy lub poziomy, można wykorzystać rozwiązanie wzorcowe z uproszczoną implementacją (chociażby dlatego, że łatwiej jest porównywać odcinki).

Podzadanie 4

Ponieważ limity pozwalają na rozwiązanie kwadratowe, nie trzeba utrzymywać set-a oraz tablicy rightmost_under, tylko wystarczy za każdym nowym aktywnym odcinkiem liniowo przeiterować się po wszystkich rozpatrzonych odcinkach i wyznaczyć odcinki pod oraz nad rozpatrywanym odcinkiem, a następnie wyznaczyć najbardziej prawy punkt iterując się po wszystkich rozpatrzonych punktach i sprawdzając (na przykład iloczynem wektorowym), czy znajduje się w obszarze.