Fişierul intrare/ieşire:lampa2.in, lampa2.outSursăLot Seniori Alexandria, 2017, baraj 4
AutorAdrian Budau, Eric StavaracheAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test0.6 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.inlampa2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?