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.
Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość
Nie możesz rozpoczynać nowych wątków Nie możesz odpowiadać w wątkach Nie możesz edytować swoich postów Nie możesz usuwać swoich postów Nie możesz dodawać załączników