Fişierul intrare/ieşire:serviciu.in, serviciu.outSursăInfoarena Monthly 2012, Runda 9
AutorAndrei GrigoreanAdăugată dedushmiMihai-Alexandru Dusmanu dushmi
Timp execuţie pe test0.125 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inserviciu.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content