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

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


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

Grădinile roditoare ale Bărăganului suferă anual pierderi imense din cauza secetei. Căutătorii de apă au găsit n fântâni din care doresc să alimenteze n grădini. Fie Gi, Fi, i=1,n puncte în plan reprezentând puncte de alimentare ale grădinilor şi respectiv punctele în care se află fântânile. Pentru fiecare punct se dau coordonatele întregi (x,y) în plan. Pentru a economisi materiale, legătura dintre o grădină şi o fântână se realizează printr-o conductă în linie dreaptă. Fiecare fântână alimentează o singură grădină. Consiliul Judeţean Galaţi plăteşte investiţia cu condiţia ca lungimea totală a conductelor să fie minimă. Fiecare unitate de conductă costă 100 lei noi (RON).

Cerinţă

Să se determine m, costul minim total al conductelor ce leagă fiecare grădină cu exact o fântână.

Date de intrare

Fişierul de intrare seceta.in va conţine:
Pe prima linie se află numărul natural n, reprezentând numărul grădinilor şi al fântânilor.
Pe următoarele n linii se află perechi de numere întregi Gx Gy, separate printr-un spaţiu, reprezentând coordonatele punctelor de alimentare ale grădinilor.
Pe următoarele n linii se află perechi de numere întregi Fx Fy, separate printr-un spaţiu, reprezentând coordonatele punctelor fântânilor.

Date de ieşire

Fişierul de ieşire seceta.out va conţine pe prima linie un număr natural m reprezentând partea întreagă a costului minim total al conductelor.

Restricţii

1 < n < 13
0 <= Gx, Gy, Fx, Fy <= 200

Nu există trei puncte coliniare, indiferent dacă sunt grădini sau fântâni.
Orice linie din fişierele de intrare şi ieşire se termină prin marcajul de sfârşit de linie.

Exemple

seceta.inseceta.outExplicaţii
3 1 4 3 3 4 7 2 3 2 9 3 1 624 Costul minim este [6.24264 * 100]=624 prin legarea perechilor:
Gradini Fantani
1 4 2 3
3 3 3 1
4 7 2 9

autor: Prof. Ovidiu Domşa
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2005: baschet, ingerasi, numar1, prieteni, robinson, aritma, cezar, cuburi2, joc8, bifo, joc9, pal, romeo, antena, avere, joc11, paianjen, suma2, vizibil, masina3, csir, lsort, patrat, ziduri, anticip, bsir, evantai, galax, spion, texan
De acelaşi autor: limbaj, pereti, poligon2, cladiri1, nivfractie
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, 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 vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor