Historia OI -> XIII OI 2005/2006 -> Zadania

SIO

MAIN

Zadanie: Żaby

Dostępna pamięc: 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: w_x i w_y oddzielone pojedynczym odstępem -- szerokość i długość pola ( 2 $$ \leq$% WIDTH=16 HEIGHT=30$ w_x, w_y $$ \leq$% WIDTH=16 HEIGHT=30$ 1 000). Drugi wiersz wejścia zawiera cztery liczby całkowite: p_x, p_y, k_x i k_y oddzielone pojedynczymi odstępami; (p_x, p_y) to początkowe położenie żaby, (k_x, k_y) to końcowe położenie żaby ( 1 $$ \leq$% WIDTH=16 HEIGHT=30$ p_x, k_x $$ \leq$% WIDTH=16 HEIGHT=30$ w_x, 1 $$ \leq$% WIDTH=16 HEIGHT=30$ p_y, k_y $$ \leq$% WIDTH=16 HEIGHT=30$ w_y). Trzeci wiersz wejścia zawiera jedną liczbę całkowitą n -- liczbę odstraszaczy rozmieszczonych na polu ( 1 $$ \leq$% WIDTH=16 HEIGHT=30$ n $$ \leq$% WIDTH=16 HEIGHT=30$ w_x^.w_y). Kolejne n wierszy zawiera współrzędne kolejnych odstraszaczy. Wiersz i + 3 dla 1 $$ \leq$% WIDTH=16 HEIGHT=30$ i $$ \leq$% WIDTH=16 HEIGHT=30$ n zawiera dwie liczby całkowite x_i i y_i oddzielone pojedynczym odstępem -- są to współrzędne i-tego odstraszacza ( 1 $$ \leq$% WIDTH=16 HEIGHT=30$ x_i $$ \leq$% WIDTH=16 HEIGHT=30$ w_x, 1 $$ \leq$% WIDTH=16 HEIGHT=30$ y_i $$ \leq$% WIDTH=16 HEIGHT=30$ w_y). Każdy odstraszacz znajduje się w innym miejscu i żaden z nich nie znajduje się w punkcie (p_x, p_y) ani (k_x, k_y).

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:

poprawną odpowiedzią jest:

Optymalna droga żaby.

Wersja do druku