Wszystko potwierdzam

Potwierdzam również testy Piotra Żurkowskiego
Łączny czas na 11plików - ~0.15s
Testy z pierwszego postu (wydajnościowe) - 0.03s


Sprzęt - Core2Duo (Mobilne) T6400 2.0GHz

Potwierdzam wszystko.

Niby potwierdzam, ale w kodzie piękny bigos ;]

@up Przy pewnym przyśpieszeniu (ok 0.5s na 4s) objętość kodu wzrosła ponad dwukrotnie ale przynajmniej czasy mniejsze :]

Kurde, mam znowu dziwny problem Otóż, jak robię testy bashową pętelką:

To... wyskakują same "NIE" Kiedy pojedyńczo je przekierowywuję, wyniki są OK. Jakieś pomysły, bo mi brakło?

Powinno być chyba

Oooj...

I tyle roboty w naprawę algorytmu (myślałem że mam błędny...), bo nie zauważyłem że to nie "i"... Chyba muszę wrócić do noszenia okularów Dzięki

Jak tam Wasze rozwiązania?

Ja zrobiłem sobie graf i kwadratowo względem ilości okręgów sprawdzałem czy odległość środków dwóch porównywanych kwadratów jest mniejsza lub równa sumie ich promieni - wtedy się stykają lub nakładają i jeśli tak - istnieje pomiędzy nimi nieskierowana krawędź. Później po prostu we wszystkich spójnych składowych zapuszczałem DFS'a i jeśli w danej spójnej składowej istniały jednocześnie okręgi, które przecinały/stykały się z lewą i prawą krawędzią - nie da się przejść

Ja użyłem Find & Union, każde przecinające się okręgi łączyły zbiory, do tego miałem wierzchołki odpowiadające przecięciu ze ścianami. Na końcu sprawdzałem czy wierzchołki odpowiadające ścianom są w jednym zbiorze.