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

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


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

Miruna deseneaza in plan N puncte. Ea defineste notiunea de arbore partial pentru un set de S puncte ca fiind o submultime de exact S-1 segmente avand capetele printre punctele date, astfel incat sa se poata ajunge dintr-un punct in oricare altul mergand pe segmentele alese. Miruna defineste si notiunea de arbore partial de cost minim ca fiind acel arbore partial pentru care suma lungimilor segmentelor din submultimea aleasa sa fie minima.

Cerinta

Dupa ce deseneaza un punct nou in plan, Miruna doreste sa afle care este suma lungimilor segmentelor ce alcatuiesc arborele partial de cost minim pentru toate punctele desenate pana in acel moment.

Date de intrare

Pe prima linie a fisierului de intrare desen.in este scris un singur numar intreg N, reprezentand numarul de puncte desenate de Miruna. Urmatoarele N linii vor contine cate 2 numere intregi, reprezentand coordantele unui nou punct desenat.

Date de iesire

Fisierului de iesire desen.out va contine N numere reale, reprezentand suma lungimilor segmentelor ce alcatuiesc un arbore partial de cost minim dupa fiecare punct desenat de Miruna.

Restrictii si precizari

  • 1 <= N <= 1000
  • Coordonatele punctelor vor fi numere intregi cuprinse intre 0 si 1000
  • Exista posibilitatea ca unele puncte sa coincida
  • Se va accepta o eroare de 0.001

Exemplu

desen.in desen.out
5
0 0
0 2
2 0
2 2
1 1
0.000000
2.000000
4.000000
6.000000
5.656854

Andrei Grigorean
Universitatea Bucuresti
Contact:grigo014@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, aven, 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, 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: fbr, 2sir, platforma, barfa, sumdif, cartonase, seif, kinder, shgraf, pikachu, dist1, subgeom, submatrix1, teroristi, parpal, bubblesort
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre APM: retea, apm, vitale, spp, urgenta
surse trimise | ajutor