W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Mirek i Sławek zostali niedawno zatrudnieni jako maszyniści w PKP. Już pierwszego dnia pracy dostali ciekawe zadanie. Każdy z nich powinien wystartować ze wcześniej ustalonego miasta i przejechać swoją lokomotywą przez jak największą liczbę miast.
Mirek ma już doświadczenie w prowadzeniu pociągu, więc nie boi się niczego. Dla Sławka jest to jednak pierwszy raz, więc nie potrafi nic samodzielnie zrobić z pociągiem. Szczęśliwie, wszystkie lokomotywy są wyposażone w walkie-talkie, więc Mirek może instruować Sławka, tak długo jak pozostają oni w zasięgu działania tego urządzenia.
Miasta są reprezentowane przez punkty na płaszczyźnie. Niektóre z nich połączone są torami kolejowymi, czyli odcinkami łączącymi dane punkty. Mirek i Sławek zaczynają swoją podróż w miastach oddalonych od siebie o co najwyżej kilometrów.
Lokomotywy mogą jeździć po torach w dowolnym kierunku i z dowolną prędkością (także robić postoje w dowolnych miejscach), ale zmieniać tor którym jadą jedynie w miastach. Mirek i Sławek w każdym momencie muszą być w odległości co najwyżej kilometrów.
Napisz program, który znajdzie wszystkie miasta, które może odwiedzić Sławek, zgodnie z zasadami opisanymi powyżej.
Napisz program, który:
Pierwszy wiersz wejścia zawiera liczby całkowite i (, ) oraz liczbę rzeczywistą (, ma co najwyżej dwie cyfry po przecinku). Oznaczają one, odpowiednio: liczbę miast, liczbę odcinków torów oraz zasięg walkie-talkie w kilometrach. Miasta są ponumerowane liczbami od do . Każdy z kolejnych wierszy zawiera współrzędne miasta na mapie , (). Kolejne wierszy opisuje sieć kolejową. W każdym z nich znajdują się dwie liczby całkowite - numery miast połączonych odcinkiem torów.
Ostatnia linia zawiera numery miast w których zaczynają swoją podróż Mirek i Sławek, w tej kolejności. Te dwa miasta nie są odległe o więcej niż kilometrów.
Wyjście powinno składać się z numerów miast, do których może dotrzeć Sławek. Numery te powinny być posortowane rosnąco i wypisane po jednej liczbie na wiersz.
Dla danych wejściowych:
5 4 1.5 0 1 0 0 4 1 4 0 2 2 1 3 1 5 3 5 2 4 2 1
poprawną odpowiedzią jest:
1 3
Zapożyczenie z chorwackiej olimpiady informatycznej: Tomasz Kulczyński.