Polish version    English version  
  Historia OI -> XIII OI 2005/2006 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 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: wx i wy oddzielone pojedynczym odstępem -- szerokość i długość pola ( 2 $ \leq$% WIDTH=16 HEIGHT=30 wx, wy $ \leq$% WIDTH=16 HEIGHT=30 1 000). Drugi wiersz wejścia zawiera cztery liczby całkowite: px, py, kx i ky oddzielone pojedynczymi odstępami; (px, py) to początkowe położenie żaby, (kx, ky) to końcowe położenie żaby ( 1 $ \leq$% WIDTH=16 HEIGHT=30 px, kx $ \leq$% WIDTH=16 HEIGHT=30 wx, 1 $ \leq$% WIDTH=16 HEIGHT=30 py, ky $ \leq$% WIDTH=16 HEIGHT=30 wy). 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 wx . wy). 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 xi i yi oddzielone pojedynczym odstępem -- są to współrzędne i-tego odstraszacza ( 1 $ \leq$% WIDTH=16 HEIGHT=30 xi $ \leq$% WIDTH=16 HEIGHT=30 wx, 1 $ \leq$% WIDTH=16 HEIGHT=30 yi $ \leq$% WIDTH=16 HEIGHT=30 wy). Każdy odstraszacz znajduje się w innym miejscu i żaden z nich nie znajduje się w punkcie (px, py) ani (kx, ky).

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
Optymalna droga żaby.





Wersja do druku