Problem 567: lampa

Ținutul ManTeleor este format dintr-un grid infinit în care există $N$ stupi de albine, pentru fiecare stup cunoscându-se poziția acestuia, dată de coordonatele întregi $XS[i]$ și $YS[i]$ . Întreg ținutul este luminat de o lampă aflată în poziția $(X_L, Y_L)$ (coordonate întregi) care luminează toate zonele aflate la o distanță Alexandria mai mică sau egală cu $D$ .

Cerință

Aladdin dorește să își construiască o casă într-o poziție $(X_C, Y_C)$ reprezentând colțul sau centrul unui pătrat din grid, astfel încât construcția să fie luminată de lampă, iar distanța Alexandria până la cel mai apropiat stup de albine să fie maximă, deoarece protagonistul nostru este apifob (se teme de albine).

Date de intrare

Fișierul lampa.in va conține pe prima linie $4$ numere întregi $N, X_L, Y_L, D$ , având semnificația din enunț. Apoi vor urma $N$ linii, conținând câte două numere întregi, reprezentând coordonatele unui stup.

Date de ieșire

Prima linie a fișierului lampa.out va conține $3$ numere: distanța Alexandria până la cel mai apropiat stup de albine, după care coordonatele casei, $X_C$ si $Y_C$ , separate prin câte un spațiu.

Restricții și precizări

$1 ≤ N, D ≤ 100 \ 000$
$-1 \ 000 \ 000 \ 000 ≤ X_L, Y_L ≤ 1 \ 000 \ 000 \ 000$
$-1 \ 000 \ 000 \ 000 ≤ X_C, Y_C ≤ 1 \ 000 \ 000 \ 000$
$-1 \ 000 \ 000 \ 000 ≤ XS[i], YS[i] ≤ 1 \ 000 \ 000 \ 000$
Casa poate fi construită în puncte de coordonate întregi sau în centrul unor pătrate din grid
Distanța Alexandria dintre două puncte aflate la coordonatele $(x_1, y_1)$ , respectiv $(x_2, y_2)$ , este definită ca $|x_1 – x_2| + |y_1 – y_2|$ , unde $|x|$ reprezintă valoarea absolută a lui $x$ .
Pentru teste în valoare de $20$ de puncte $N ≤ 200, D ≤ 100$
Pentru teste în valoare de alte $20$ de puncte $N ≤ 500, D ≤ 600$
Pentru teste în valoare de alte $20$ de puncte $D ≤ 750$

Exemplu:

lampa.in

lampa.out

11 8.0 3.0

Explicație

Dacă ne alegem casa în punctul de coordonate $(8, 3)$ , cel mai apropiat stup va fi la distanța Alexandria $11$ .

lampa