.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » aven

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
aven


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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:


prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2007: perechi, teanc, index, light, copaci, teren, pizza, grupe, cod, ecran, drum, soldati, factura, palma, decript, lbd, cs, h, trenuri, sort, spam, complex, parent, holo, tren2, gray, siruri, arce, pasi, cifre, mgo, firma, joc, cartonase, vikingi, anagrame, balbe, vecini, balaur, tribile, conflicte, criptmat, mesaj, maxim, magic3, desen, plimbare, cutie, patrate, party, vagoane, robot, astre, trains, numere2, friends, tricouri, furtuna, net, baby, scaune, 3d, axa, bile2, vmem, pahare, termen, sablon, zapada, cuvinte, excursie, hd, pajura, pc, sir, cadere, pioni
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre geometrie: forum, supertri, ozn, detinut, atac, afise, mere, ff, teren, volei, patrate, robot, pahare, pendul, robot2, dragon, poligon, druid, laser, patrate3, ploaia, donald, lot, atac1, arcas, paralel, dotnet, aedaro, vectori, spirala, distanta, triunghi, center, harta1, seceta, antena, poligon1, benzina, zoo, texan, oypara, dreptc, mosia, sea, poligon3, poligon2, snipers, basm, cetati, placa, nori, cerc, smin, cern, cuiburi, acerc, select, proiect, poligon4, terenuri, monoton, acoperire, capra, testament, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
Despre căutare binară: gropi, pod, uscat, checkin, copaci, br, furtuna, livada, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, centru, harta1, salvare, spion, poze, dist1, patrate5, resturi, lanterna, sea2, vot, standard, cantor, medalii, binperm, mobil, stalpi1, expo, miere, conferinta, subs, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, ssk, robotics, cabana
Software recomandat
surse trimise | ajutor