6
0 10
3 7
5 0
6 1
7 4
10 5
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:
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
| aven.in | aven.out | aven.in | aven.out | Explicatie |
| 6 |
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:
|
Timp maxim de executie/test: 0.1 secunde
prof. Emanuela
Cerchez
Liceul de Informatica
"Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com