
Re: [Dlaczego Oni Śpiewają] Testy
Ja jeszcze inaczej to napisałem.
Sprawdzałem posortowane kolejno (od lewej strony) okręgi czy aby są styczne z którymś z poprzednich (który zaś styka się z lewą ścianą (bez)pośrednio). Dla każdego okręgu szukałem (dopóki nie znajdę, lub dopóki prawa ściana poprzedniego jest dalej lub na równi z lewą ścianą aktualnego) wszystkie okręgi. Jeśli było tak - sprawdzałem czy są styczne, jeśli były - sprawdzałem czy tamten był połączony z lewą ścianą. Oczywiście trochę optymalizacji coby nie szło jako k^2. Po zakończeniu spr. (jeśli udało się połączyć bądź z jakimś poprzednim (który łączy się z lewą ścianą) bądź z samą lewą ścianą) spr. czy łączy się aktualny z prawą - jeśli tak to nie można przejść i koniec pętli, jeśli nie to jedzie dalej lub - jeśli to koniec okręgów - można przejść.
Maxymalny czas: x (po 22)
@Paweł Michalak - Może i wygląda na k^2, ale praktycznie k^2 nigdy nie osiągnę w samym algorytmie, nawet blisko niego nie podejdę. Zapomniałem jedynie policzyć sortowania - k*log(k) (dla max testu to 3000 obrotów). Zakładając że każdy jest połączony z poprzednim mam 4k obrotów - czyli do 1mln trochę brakuje

Do tego dochodzi jeszcze to, że w zależności od pozycji kolejnych okręgów badam tylko kilka okręgów ostatnich, więc szczerze wątpię aby dla maksymalnych danych zrobiło ten milion obrotów.
Przynajmniej tak mi się wydaje i rzucając kilka "najgorszych" testów dla algorytmu wykazuje, że łącznie z posortowaniem robi mniej obrotów niż k^2

A jak z czasem - zobaczymy, zawsze mogłem coś "zepsuć"
