| Fişierul intrare/ieşire: | lampa2.in, lampa2.out | Sursă | Lot Seniori Alexandria, 2017, baraj 4 |
| Autor | Adrian Budau, Eric Stavarache | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Lampa2
Ţ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 (XL, YL) (coordonate întregi) care luminează toate zonele aflate la o distanţă Alexandria mai mică sau egală cu D.
Aladdin doreşte să îşi construiască o casă într-o poziţie (XC, YC) 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 lampa2.in va conţine pe prima linie 4 numere întregi N, XL, YL, 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 lampa2.out va conţine 3 numere: distanţa Alexandria până la cel mai apropiat stup de albine, după care coordonatele casei, XC si YC, separate prin câte un spaţiu.
Restricţii şi precizări
- 1 ≤ N, D ≤ 100.000
- -1.000.000.000 ≤ XL, YL ≤ 1.000.000.000
- -1.000.000.000 ≤ XC, YC ≤ 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 (x1, y1), respectiv (x2, y2), este definită ca |x1 – x2| + |y1 – y2|, 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 ≤ 550, D ≤ 600
- Pentru teste în valoare de alte 20 de puncte D ≤ 750
Exemplu
| lampa2.in | lampa2.out |
|---|---|
| 3 6 3 2 2 9 1 -1 -2 1 | 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.
