Explorand
o pestera din muntii Apuseni, Ion a descoperit un aven si vrea sa-l cerceteze.
In acest scop, Ion trebuie sa instaleze o lampa care sa ilumineze in intregime
peretele avenului. Peretele avenului are forma unei linii frante (o succesiune
de segmente de dreapta, cu proprietatea ca extremitatea initiala a fiecarui
segment, exeptand primul, coincide cu extremitatea finala a segmentului precedent).
Vom denumi extremitatile acestor segmente varfuri. Datorita formei pe care o
are avenul, varfurile sale au abscisele in ordine crescatoare.
Consideram ca lampa ilumineaza in intregime peretele avenului daca orice punct
de pe peretele avenului poate fi unit printr-un segment de dreapta cu punctul
in care este plasata lampa, evident, fara ca segmentul respectiv sa "traverseze"
peretele avenului. Segmentul respectiv poate insa sa fie plasat de-a lungul
unuia dintre segmentele ce constituie peretele avenului sau sa treaca printr-un
varf, fara insa a "traversa" peretele.
Cerinta
Sa se determine inaltimea
minima la care poate fi plasata lampa, astfel incat sa ilumineze in intregime
peretele avenului. Inaltimea este masurata de la axa Ox (deci reprezinta ordonata
punctului in care este plasata lampa).
Date de
intrare
Fisierul de intrare aven.in
contine doua linii. Pe prima linie se afla un numar natural N
reprezentand numarul de varfuri. Urmatoarele N
linii contin coordonatele varfurilor (in ordinea abscisa, ordonata), cate un
varf pe o linie. Varfurile sunt specificate in ordinea crescatoare a absciselor
lor.
Date de
iesire
Fisierul de iesire aven.out
va contine o singura linie pe care va fi scris un numar real (rotunjit la doua
zecimale) care reprezinta ordonata punctului in care va fi plasata lampa (minima
posibil).
Restrictii
si precizari
2 <= N <= 5000
0 <= abscisa,
ordonata <= 100 000
Rezultatul este considerat
corecta daca diferenta in valoare absoluta intre rezultatul afisat si cel
corect este <= 0.01.
Pentru datele de test
rezultatul va fi <= 1 000 000.
Exemple
aven.in
aven.out
aven.in
aven.out
Explicatie
6
0 10
3 7
5 0
6 1
7 4
10 5
3.75
6
1 1
4 2
5 0
9 2
12 3
16 4
2.00
Pentru
primul exemplu, configuratia avenului si pozitia lampii este ilustrata
in figura urmatoare: