In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.