Żaby
Limit pamięci: 64 MB
W Bajtocji zapanowała klęska żab - niszczą one wszystkie
uprawy.
Rolnik Bajtazar postanowił walczyć z żabami za pomocą specjalnych
odstraszaczy, które rozmieścił w wybranych miejscach
na swoim polu.
Każda żaba, przemieszczając się z jednego miejsca do drugiego, stara się
omijać odstraszacze w jak największej odległości, tzn.
maksymalizuje odległość od najbliższego odstraszacza.
Pole Bajtazara ma kształt prostokąta.
Żaby skaczą po polu równolegle do boków pola, przemieszczając się w
każdym pojedynczym skoku o jedną jednostkę.
Odległość od odstraszaczy jest rozumiana jako minimum z odległości od
poszczególnych odstraszaczy dla wszystkich pozycji, na których żaba się
znajdowała.
Bajtazar wie skąd i dokąd żaby się najczęściej przemieszczają i
eksperymentuje z różnymi rozmieszczeniami odstraszaczy.
Poprosił Cię o pomoc, chce abyś napisał program obliczający
dla zadanego rozstawienia odstraszaczy, w jakiej odległości od
odstraszaczy
żaby mogą przedostawać się po jego polu z jednego miejsca do drugiego.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia rozmiar pola, rozmieszczenie
odstraszaczy oraz pozycję początkową i końcową żaby,
-
wyznaczy maksymalną odległość od najbliższego odstraszacza, przy
jakim żaba będzie musiała przejść na swojej drodze,
-
wypisze kwadrat znalezionej odległości na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite:
i oddzielone pojedynczym odstępem
- szerokość i długość pola ().
Drugi wiersz wejścia zawiera cztery liczby całkowite:
, , i oddzielone pojedynczymi odstępami;
to początkowe położenie żaby,
to końcowe położenie żaby
(, ).
Trzeci wiersz wejścia zawiera jedną liczbę całkowitą
- liczbę odstraszaczy rozmieszczonych na polu
().
Kolejne wierszy zawiera współrzędne kolejnych odstraszaczy.
Wiersz dla zawiera dwie liczby
całkowite i oddzielone
pojedynczym odstępem - są to współrzędne -tego odstraszacza
(, ).
Każdy odstraszacz znajduje się w innym miejscu i żaden z nich
nie znajduje się w punkcie ani .
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna
liczba całkowita, kwadrat maksymalnej odległości na jaką żaba musi
się zbliżyć do najbliższego odstraszacza.
Jeżeli żaba nie może uniknąć wskoczenia bezpośrednio na odstraszacz,
to wynikiem jest 0.
Przykład
Dla danych wejściowych:
5 5
1 1 5 5
2
3 3
4 2
poprawną odpowiedzią jest:
4
Optymalna droga żaby.
Autor zadania: Piotr Stańczyk.