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

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


Timp maxim de execuţie / test:
2s
Memorie totala disponibilă / stivă:
32MB / 1MB

Scrierea numelor localităţilor pe o hartă a fost întotdeauna o problemă importantă a cartografilor, deoarece dacă unele nume s-ar suprapune harta ar deveni ilizibilă.
Se cunosc coordonatele carteziene ale punctelor care marchează pe hartă localităţile. Pentru fiecare localitate marcată pe hartă trebuie să scriem numele său. Numele unei localităţi trebuie să fie încadrat într-un dreptunghi care îndeplineşte următoarele condiţii:
– are laturile paralele cu axele de coordonate;
– lăţimea dreptunghiului este egală cu triplul înălţimii dreptunghiului;
– punctul care marchează pe hartă localitatea să fie plasat în colţul stânga sus al dreptunghiului.
Dreptunghiurile în care sunt scrise numele localităţilor trebuie să aibă toate aceleaşi dimensiuni.

Cerinţă

Scrieţi un program care să determine înălţimea maximă a dreptunghiului care încadrează numele localităţilor, astfel încât oricare două dreptunghiuri desenate pe hartă să aibă intersecţia de arie 0.

Date de intrare

Fişierul harta1.in conţine pe prima linie un număr natural N reprezentând numărul de localităţi marcate pe hartă. Pe fiecare dintre următoarele N linii se află câte două numere naturale X Y, reprezentând coordonatele punctelor (abscisă, ordonată) care marchează pe hartă localităţile.

Date de ieşire

Fişierul harta1.out va conţine o singură linie pe care va fi scris un număr real cu 3 zecimale care reprezintă înălţimea maximă a dreptunghiurilor care încadrează numele localităţilor, astfel încât oricare două dreptunghiuri să aibă intersecţia de arie 0.

Restricţii

1 < N ≤ 1 000 000
0 ≤ X, Y ≤ 1 000 000

Oricare două puncte de pe hartă sunt distincte.
Rezultatul va fi considerat corect dacă diferenţa în valoare absolută dintre rezultatul corect şi cel din fişierul de ieşire este <0.01.

Exemple

harta1.inharta1.out
5 1 1 6 5 18 3 9 9 16 15 4.000
10 26 77 12 37 14 18 19 96 71 95 91 9 98 43 66 77 2 75 94 91 7.667

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot AB 2007: casute, centru, imax, sir1
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, aven, 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, 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, aven, patrate, robot, pahare, pendul, robot2, dragon, poligon, druid, laser, patrate3, ploaia, donald, lot, atac1, arcas, paralel, dotnet, aedaro, vectori, spirala, distanta, triunghi, center, 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 hashing: poze, parpal, radio1, oldest, aranjare1
Despre căutare binară: gropi, pod, uscat, checkin, copaci, aven, br, furtuna, livada, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, centru, 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