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

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


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

Mădălina este înnebunită după probleme de geometrie. De data aceasta ea are N puncte de coordonate reale în plan şi doreşte să acopere punctele cu cercuri care au centrele pe axa OX (axa absciselor) astfel încât suma ariilor cercurilor să fie minimă.

Cerinţă

Cunoscând coordonatele celor NN puncte în plan, găsiţi o acoperire a acestor puncte cu cercuri ce au centrele aflate pe axa OX, astfel încât suma ariilor cercurilor să fie minimă.

Date de intrare

Pe prima linie a fişierului de intrare acerc.in se va afla numărul natural N. Următoarele N linii vor conţine fiecare câte două numere reale X şi Y, separate prin spaţiu, reprezentând coordonatele punctelor.

Date de ieşire

Pe prima linie a fişierului de ieşire acerc.out veţi afişa un singur număr reprezentând suma minimă a ariilor cercurilor ce respectă condiţia din cerinţă.

Restricţii

1 ≤ N ≤ 300
• Valorile coordonatelor punctelor vor fi în intervalul [-10 000, 10 000]
• Un cerc acoperă toate punctele din plan aflate faţă de centrul acestuia la o distanţa mai mică sau egală cu raza cercului.
• Diferenţa maximă cu care rezultatul final poate varia faţă de cel corect este de 0.001

Exemple

acerc.inacerc.outExplicaţii
7 0 2 1 1 1 3 4 0 3.9 2 8 4 7 4 79.6208 Se vor acoperi cele 7 puncte cu două cercuri: unul cu centrul în punctul (0, 1) şi raza egală cu 3 şi unul cu centrul în punctul (0, 7.41341) şi raza egală cu 4.04278

autor: Cosmin Gheorghe
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot AB 2010: codif, game1, piatra, miere, left, autostrazi, bubblesort, carray, hawaii, radio1, randomizare, tetris1, trenuri1
De acelaşi autor: diff, kmax, kdtree, intervale
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
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, harta1, seceta, antena, poligon1, benzina, zoo, texan, oypara, dreptc, mosia, sea, poligon3, poligon2, snipers, basm, cetati, placa, nori, cerc, smin, cern, cuiburi, select, proiect, poligon4, terenuri, monoton, acoperire, capra, testament, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
surse trimise | ajutor