wx, wy 1 000W 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.
wx, wy 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 px, kx wx,
1 py, ky wy).
Trzeci wiersz wejścia zawiera jedną liczbę całkowitą
n -- liczbę odstraszaczy rozmieszczonych na polu
(
1 n wx . wy).
Kolejne n wierszy zawiera współrzędne kolejnych odstraszaczy.
Wiersz i + 3 dla
1 i n zawiera dwie liczby całkowite xi i yi oddzielone
pojedynczym odstępem -- są to współrzędne i-tego odstraszacza
(
1 xi wx,
1 yi wy).
Każdy odstraszacz znajduje się w innym miejscu i żaden z nich
nie znajduje się w punkcie
(px, py) ani
(kx, ky).
5 5 1 1 5 5 2 3 3 4 2poprawną odpowiedzią jest:
4
