| Fişierul intrare/ieşire: | serviciu.in, serviciu.out | Sursă | Infoarena Monthly 2012, Runda 9 |
| Autor | Andrei Grigorean | Adăugată de |  Mihai-Alexandru Dusmanu •dushmi |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Serviciu
Orasul Ciclonia este unul mai special deoarece atat casele, cat si birourile sunt asezate pe un cerc. Numarul total de locuitori ai orasului este N, fiecare dintre acestia avand o casa si un birou propriu, deci in total exista 2 * N constructii. Distanta intre oricare doua cladiri consecutive este egala cu 1. Stiind ca oamenii merg la serviciu pe drumul cel mai scurt, sa se determine distanta maxima pe care o va parcurge un locatar intre casa si biroul sau.
Date de intrare
Fişierul de intrare serviciu.in va contine pe prima linie numarul de locatari din orasul Ciclonia, N. Urmatoarele N linii vor contine cate doua numerele, pe linia i + 1 aflandu-se coordonatele casei si biroului locatarului i (in aceasta ordine).
Date de ieşire
În fişierul de ieşire serviciu.out se va afisa pe prima linie distanta maxima pe care o va parcurge un locatar intre casa lui si locul sau de munca.
Restricţii
- 1 ≤ N ≤ 100 000
- Se garanteaza ca nu vor exista 2 constructii la aceasi coordonata.
Exemplu
| serviciu.in | serviciu.out |
|---|---|
| 3 1 4 5 3 2 6 | 3 |
Explicaţie
Distantele de la casa locatarului 1 pana la biroul sau sunt 3 si respectiv 3, deci el poate merge pe oricare dintre cele doua drumuri de lungime 3.
Distantele de la casa locatarului 2 pana la biroul sau sunt 2 si respectiv 4, deci el merge pe drumul de lungime 2.
Distantele de la casa locatarului 3 pana la biroul sau sunt 4 si respectiv 2, deci el merge pe drumul de lungime 2.
In imaginea de mai jos se pot vedea pozitiile constructiile din orasul Ciclonia pentru configuratia din exemplu (punctele albastre sunt birourile, iar cele rosii sunt locuintele).
