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

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


Timp maxim de execuţie / test:
4.2s
Memorie totala disponibilă / stivă:
64MB / 8MB

James Bond (JB) are o nouă misiune: trebuie să distrugă N planete bidimensionale, pe care se află baze secrete (evident nu şi pentru JB) ale răufăcătorilor. Fiecare planetă are forma unui cerc, având pe circumferinţa sa un anumit număr de baze secrete.
JB va trebui să plaseze câte o singură bombă pe fiecare planetă. Bomba poate fi plasată în oricare dintre bazele secrete ale planetei. După plasarea bombei, JB se deplasează spre o altă planetă în linie dreaptă, putând ateriza doar într-una din bazele secrete ale acesteia. După ce aterizează pe o nouă planetă, JB poate să se deplaseze sau nu pe circumferinţa acesteia până la oricare altă bază secretă, după care va plasa o bombă şi va pleca spre o altă planetă.
JB nu poate reveni pe o planetă pe care a aterizat anterior.
JB are la dispoziţie trei vehicule de transport:
• teleportatorul: cu ajutorul căruia se poate deplasa între oricare două baze secrete de pe planete diferite.



• dietatietorul: cu ajutorul căruia se poate deplasa între oricare două baze secrete de pe planete diferite, dacă drumul nu intersectează interioarele planetelor de plecare şi/sau destinaţie. El poate intersecta suprafaţa altor planete. (vezi desenele de mai jos)



• deltaplanorul: cu ajutorul acestuia se poate deplasa între oricare două baze secrete de pe planete diferite, dacă drumul nu intersectează nicio planetă (inclusiv cea de plecare si cea de destinaţie).



Oricare ar fi vehiculul folosit, JB se va mişca între două baze ale aceleiaşi planete doar pe circumferinţa cercului, iar distanţa totală parcursă va fi suma lungimilor drumurilor curbilinii împreună cu lungimea drumurilor drepte parcurse.
În misiune, JB poate folosi doar unul dintre cele trei vehicule de transport. El vă roagă pe voi să-i calculaţi distanţa minimă pe care ar trebui să o parcurgă cu ajutorul fiecărui vehicul disponibil.
Eroul nostru îşi poate începe misiunea pe orice bază a oricărei planete. Misiunea se va încheia imediat ce au fost plasate bombe pe toate planetele. În acel moment JB le va distruge prin declanşarea simultană a tuturor bombelor.

Cerinţă

Determinaţi cele trei distanţe minime.

Date de intrare

Pe prima linie a fişierului jb.in se află N - numărul de planete. Pe următoarele 2*N linii sunt descrise cele N planete, câte două linii pentru fiecare planetă. Pe prima linie din descrierea planetei i se găsesc patru numere: Xi Yi Ri Bi, reprezentând coordonatele centrului, raza, şi numărul de baze secrete de pe planeta i.
Pe a doua linie se găsesc Bi perechi de numere reale, reprezentând coordonatele bazelor de pe planeta i.

Date de ieşire

Fişierul de ieşire jb.out va conţine trei linii, pe fiecare linie fiind scris câte un număr real, reprezentând în ordine costurile minime în cazul folosirii teleportatorului, dietatietorului respectiv a deltaplanorului.

Restricţii

• 1 ≤ N ≤ 10
• 1 ≤ Bi ≤ 50
• -1 000 000 ≤ Xi, Yi ≤ 1 000 000
• 0 ≤ Ri ≤ 100 000
Dacă nu există nicio soluţie pentru un anumit vehicul, afişaţi -1.
Numerele se vor afişa cu 6 zecimale.
În cele zece teste N va lua următoarele valori: 2 3 5 6 7 8 10 10 10 10.
Pentru fiecare test se vor acorda: 3 puncte dacă primul număr este corect, 3 puncte dacă al doilea număr este corect şi 4 puncte daca al treilea număr este corect.
Un număr se consideră corect dacă diferă prin cel mult 0.0001 de valoarea corectă.

Exemple

jb.injb.out
3 100 100 10 4 90 100 100 110 110 100 100 90 0 50 10 3 -10 50 0 60 0 40 0 100 10 2 10 100 -10 100 121.231056 161.415927 161.415927

autor: Marius Dumitran
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la LOT SB 2011: cifre4, grad2, risipa, liste, pixy, domino2, neconex, testament, enigma, asfalt1, intervale, lant1, lcdr, jocs
De acelaşi autor: cuiburi, lcdr
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, acerc, 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, 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, acerc, select, proiect, poligon4, terenuri, monoton, acoperire, capra, testament, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
Despre backtracking: acop, bipal, magic2, vagoane, friends, tricouri, festival, numar, pento, ro, jobs, onu2, sir3, cai1, labirint, dans, ham, sudoku, caramele, linie, puncte, castel, excursia, joc7, pattern, avere, paianjen, medii, monkey, scara1, numere8, banda1, spirala1, cofetar, gradina, placa, smin, jucarii, immortal, concat, cubinvers, codif, izvor, avioane, prisme, triburi1, genab, dineu, antitero, ornament, virgule
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor