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

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


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

Un robot zburator se afla intr-un plan la coordonate cunoscute. La fiecare pas, robotul se poate deplasa in zbor in orice directie, dar continuu in linie dreapta si nu se poate opri decat atunci cand intalneste un obstacol sau ajunge la destinatie. Obstacolele sunt cercuri in interiorul carora robotul nu poate intra, dar pe extremitatea carora poate merge liber pe pamant. Dupa ce ajunge pe un cerc si se deplaseaza eventual pe acesta, robotul trece la urmatorul pas si porneste din nou in zbor, iar, pana ajunge la alt obstacol sau la destinatie, si asa mai departe. Destinatia robotului este un punct cunoscut din plan. Asadar deplasarea robotului este o succesiune alternanta de zboruri in linie dreapta si deplasari in mers pe extremitatile obstacolelor. De fiecare data cand robotul porneste in zbor consuma 1 litru de kerosen, dar odata pornit el nu mai consuma nimic, indiferent de lungimea deplasarii in zbor sau eventual lungimea deplasarii in mers de dupa zbor.

Cerinta

Cunoscand punctul in care se afla initial robotul, punctul destinatie si configuratia tuturor obstacolelor, determinati consumul minim in litri kerosen cu care robotul poate ajunge la destinatie.

Date de intrare

Pe prima linie a fisierului robot.in se gasesc cinci numere naturale separate prin spatii n, xs, ys, xf, yf. Numarul n reprezinta numarul de obstacole, (xs, ys) este punctul unde se afla initial robotul, (xf, yf) este punctul destinatie. Fiecare dintre urmatoarele n linii contine cate 3 numere naturale x, y, r, unde (x, y) este centrul unui obstacol, iar r este raza acestuia.

Date de iesire

Prima linie a fisierului robot.out va contine un singur numar natural reprezentand numarul minim de litri de kerosen folositi pentru deplasarea pana la punctul final.

Restrictii si precizari

  • 0 <= n <= 150
  • Toate coordonatele din fisierul de intrare si razele cercurilor sunt numere naturale <= 10000
  • Daca traiectoria in zbor a robotului este tangenta la un cerc, el este obligat sa se opreasca pe acel cerc.
  • Oricare ar fi doua cercuri, ele nu se intersecteaza, nu sunt unul in interiorul celuilalt, si nici un cerc nu contine punctul initial sau destinatia.
  • Oricare ar fi trei cercuri, nu exista o nici dreapta care sa fie tangenta la toate cele trei cercuri.
Exemplu
robot.in robot.out Explicatie

2 2 2 16 6
6 4 3
12 5 2

3

Traiectoria robotului poate fi cea desenata cu rosu:

stud. Paul Diac
Universitarea « Al. I Cuza », Iasi – Facultatea de Informatica
Contact:diac_paul@yahoo.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, desen, plimbare, cutie, patrate, party, vagoane, 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: mod3, excursie, cantor, fibgcd, acoperire, colina, piscina, barci
Despre geometrie: forum, supertri, ozn, detinut, atac, afise, mere, ff, teren, volei, aven, patrate, 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, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, 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 drum minim: miniasm, furtuna, excursie, arthur, bete, zmeu, trafic, masina1, bomboane, traseu, litoral, lover, trip, scara2, team, gard, pitici1, base3, coach, lanturi, trmv, pestera, fluviu, ubuntzei, razboi, benzina2, kubus2, megascoala, dragoni
surse trimise | ajutor