Runda 2: Witraż (rozwiązanie)

Autor zadania: Marcin Dublański

Algorytm opiera się na następującym spotrzeżeniu:
Jeżeli narysowaliśmy już n prostych, tworzących L obszarów, i chcemy dodać do nich jeszcze jedną prostą l o ustalonym kierunku, to liczba obszarów po dodaniu będzie co najwyżej równa L+K+1, gdzie K jest ilością już narysowanych prostych o innym kierunku niż prosta l.

Fakt ten można wręcz zobaczyć, rysując przykładową sytuację na kartce. Udowodnić zaś można go np. z twierdzenia Eulera. Wynika z niego od razu poprawność następującego algorytmu:

wynik = 1; // na poczatku jest jeden obszar
for i=1 to n do
   dodaj = 0;
   for j=1 to i-1 do
     if(prosta i może przeciąć prostą j) // czyli gdy ich kierunki są różne
     dodaj = dodaj+1;
   endfor
   wynik = wynik + dodaj + 1;
endfor

Niestety, działa on kwadratowo ze względu na ilość prostych na wejściu. Ponieważ mogło być ich nawet 200000, algorytm ten dawał szanse na zdobycie jedynie połowy punktów. Można go znacznie przyspieszyć. Skorzystamy z tego, że dwie proste na początku równoległe po przesunięciu dalej będą równoległe (czyli na pewno się nie przetną). Podzielmy zatem wszystkie proste na zbiory prostych o tym samym kierunku (np. sortując je ze względu na kierunek). Jeżeli liczności tych zbiorów wynoszą kolejno: a_1, a_2, ..., a_k, to ilość wszystkich punktów przecięcia na witrażu jest równa:

ilosc_punktow = a_1 * (a_2+a_3+a_4+...+a_k) + a_2 * (a_3+a_4+a_5+...+a_k) + ... + a_{k-1} * a_k =
= a_1 * (n - a_1) + a_2 * (n - a_1 - a_2) + ... + a_{k-1} * (n - a_1 - a_2 - ... - a_{k-1})

którą to wartość można policzyć liniowo ze względu na k.

Pozostaje zauważyć, że ostateczny wynik jest równy: ilosc_punktow + n + 1. Dlaczego tak? +1 bierze się stąd, że na początku jest jeden obszar. +n z tego samego powodu, dla którego w poprzednim algorytmie mieliśmy wynik = wynik + dodaj + 1, nie zaś wynik = wynik + dodaj. Widać więc, że najwięcej czasu zabiera sortowanie prostych. Cały algorytm działa więc liniowo-logarytmicznie, co w zupełności wystarcza na zdobycie 10 punktów.