CERC 2010: Szkice rozwiązań

28.11.2010

B: Beasts

Treść (pdf) | wyślij rozwiązanie.

Brzeg górnego (lub dolnego) szarego regionu będziemy nazywać górną (dolną) otoczką danego zbioru linii. Ponieważ celem jest wyznaczenie odległości pomiędzy dwiema takimi otoczkami, zaczniemy od ich skonstruowania. Ponieważ sytuacja jest symetryczna, skoncentrujemy się na górnej otoczce, reprezentowanej przez ciąg odcinków, gdzie pierwszy i ostatni odcinek jest półprostą.

Zaczniemy od przekształcenia wszystkich równań prostych do postaci y=Ax+B i obserwacji, że jeśli przeglądamy otoczkę od lewej do prawej, współczynniki kierunkowe tych prostych (tj. współczynniki A) są ściśle rosnące. Sugeruje to, że możemy posortować linie względem tych współczynników, a następnie dodawać je kolejno, aktualizując bieżącą otoczkę. Dodawanie linii, której współczynnik kierunkowy jest większy niż współczynniki już przetworzonych linii wymaga:

  1. usunięcia (być może pustego) sufiksu bieżącej listy odcinków opisujących otoczkę,
  2. podzielenia ostatniego odcinka na dwie części i usunięcia prawej z nich,
  3. dodania nowej półprostej zaczynającej się w punkcie przecięcia.

Kroki te zostały przedstawione na poniższym rysunku,

adding a line

Zakładając, że odcinki są utrzymywane na posortowanej liście, wszystkie operacje mogą być wykonane w zaamortyzowanym czasie stałym. Konieczne jest wykorzystanie tylko kilku geometrycznych procedur: sprawdzania czy punkt leży po prawej stronie prostej i obliczania przecięcia dwóch odcinków.

Problem został teraz zredukowany do obliczenia odległości między dwoma zbiorami odcinków. Łatwo zauważyć, że najmniejsza taka odległość jest realizowana przez parę punktów p i q taką, że p lub q jest końcem pewnego odcinka. Dlatego też dla każdego punktu górnej (dolnej) otoczki należy znaleźć najbliższy mu punkt z dolnej (górnej) otoczki. Otoczki są wypukłymi wielokątami (otwartymi z jednej strony), więc można tu zastosować standardową ogólną procedurę geometryczną. W tym zdaniu sytuacja jest mniej skomplikowana, gdyż można wykorzystać pojedyncze wyszukiwanie binarne. Zamiennie można też zaobserwować, że jeśli przesuwamy punkt p na górnej otoczce w prawą stronę, najlepszy dla niego punkt q na dolnej otoczce przesuwa się również w prawo. Umożliwia to uzyskanie czasu liniowego dla tej części problemu.

Całkowita złożoność rozwiązania to O(n log n), gdyż musimy posortować linie względem ich współczynników kierunkowych.

Informacje dodatkowe

Zasada, którą kierowaliśmy się przy układaniu testów do wszystkich zadań była taka, że wszystkie testy o rozmiarze większym niż 20 bajtów muszą być generowane przez program. Ciekawostką jest to, że testy do tego zadania (jako jedyne) nie zostały wygenerowane przez program w C++, lecz program do symbolicznych obliczeń numerycznych maple, a ich generowanie trwało każdorazowo około godziny.

Ku naszemu zdziwieniu, tego zadania również nie rozwiązał żaden zespół, choć parę próbowało.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com