Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare Urmatoarea versiune Ambele părți următoarea reviziune | ||
teme:tema2 [2017/02/14 23:49] florina_elena.barbu |
teme:tema2 [2017/04/09 13:45] mihai.iacov [Precizări] |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
====== Tema 2: GPS tracker ====== | ====== Tema 2: GPS tracker ====== | ||
- | < | ||
- | <h2 id=" | + | ===== Obiective ===== |
- | <div class=" | + | |
- | < | + | |
- | <li class=" | + | |
- | <li class=" | + | |
- | </ | + | |
- | </ | + | |
- | < | + | * Înțelegerea conceptului de graf și a modurilor de parcurgere aferente |
- | <div class=" | + | * Aplicarea algoritmilor studiați pe topologie graf într-un exemplu practic |
- | < | + | |
- | | + | |
- | | + | ===== Descriere ===== |
- | </p> | + | |
- | < | + | Sistemul Global de Poziționare (sau GPS) este o rețea de aproximativ 30 de sateliți care orbitează în jurul Pământului, |
- | | + | Acesta a fost dezvoltat de guvernul Statelor Unite în scop militar, dar oricine folosește acum un dispozitiv GPS poate recepționa semnalele radio pe care sateliții le fac broadcast. |
- | </ | + | |
- | <p> | + | |
- | | + | |
- | </ | + | |
- | <p> <h3> Trilaterația (măsurarea distanțelor, | + | |
- | Imaginează-ți că stai undeva pe Pământ cu 3 sateliți deasupra ta. Dacă știi cât de departe ești de satelitul A, atunci trebuie să te afli undeva în cercul roșu. Dacă consideri la fel pentru sateliții B și C, poți afla locația ta precisă calculând intersecția celor 3 cercuri. </ | + | |
- | Asta este ceea ce receiver-ul GPS-ul tău face, deși acesta consideră sfere suprapuse (pentru simplificare, | + | |
| | ||
+ | Oriunde te afli pe planetă, cel puțin 3 sateliți sunt ' | ||
+ | | ||
+ | Odată ce acesta are informații despre cât de departe cei trei sateliți sunt, receiver-ul GPS poate indica locația folosind un proces numit **trilaterație** . | ||
+ | | ||
+ | === Trilaterația (măsurarea distanțelor, | ||
+ | Imaginează-ți că stai undeva pe Pământ cu 3 sateliți deasupra ta. Dacă știi cât de departe ești de satelitul A, atunci trebuie să te afli undeva în cercul roșu. Dacă consideri la fel pentru sateliții B și C, poți afla locația ta precisă calculând intersecția celor 3 cercuri. | ||
+ | Asta este ceea ce receiver-ul GPS-ul tău face, deși acesta consideră sfere suprapuse. | ||
+ | |||
+ | < | ||
<img src="/ | <img src="/ | ||
<img src="/ | <img src="/ | ||
- | | + | |
+ | |||
+ | ===== Precizări ===== | ||
+ | |||
+ | Vom considera ca fișier de intrare // | ||
+ | |||
+ | Pe următoarele linii vom avea pentru fiecare locație: | ||
+ | | ||
+ | * | ||
+ | * raza R satelit1 | ||
+ | * | ||
+ | * raza R satelit2 | ||
+ | * | ||
+ | * raza R satelit3 | ||
+ | |||
+ | \\ | ||
+ | Coordonatele și raza se consideră date de fiecare satelit pentru fiecare dintre cele N locații.\\ | ||
+ | |||
+ | Datorită distanței mult mai mari de la Pământ la sateliți, față de diferența de înălțime între sateliți, ei se pot considera în același plan (z1 = z2 = z3 = z). Între cele 3 sfere există așadar cel mult 2 puncte de intersecție, | ||
+ | |||
+ | |||
+ | <note important> | ||
+ | Pentru simplificarea modelului problemei, considerăm doar proiecțiile sferelor, și presupunem că acestea se vor intersecta doar într-un singur punct (cara va reprenzenta locația propriu-zisă) \\ \\ | ||
+ | Atenție: pentru a nu greși la calcule, se recomandă scrierea ecuațiilor celor 3 cercuri și aflarea coordonatelor unei locații prin calcularea punctului de intersecție; | ||
+ | </ | ||
| | ||
- | </ | + | Se consideră prima coordonată calculată, locul din care plecăm. |
- | </ | + | |
- | <h2>Cerințe și punctaj | + | Știind coordonatele tuturor locațiilor, |
+ | <note tip> | ||
+ | Pentru punctele P1(x1, y1) şi P2(x2, y2) putem scrie ecuaţia distanţei: P1P2 = dist(P1,P2) = **sqrt( (x1-x2)< | ||
+ | </ | ||
+ | |||
+ | Vom primi un update printr-un fișier // | ||
- | < | + | ===== Cerințe ===== |
- | <div class=" | + | |
- | < | + | |
- | <li class=" | + | |
- | <li class=" | + | |
- | <li class=" | + | |
- | <li class=" | + | |
- | <li class=" | + | |
- | </ | + | |
- | </ | + | |
+ | Executabilul obținut în urma compilării va avea numele **// | ||
+ | |||
+ | <note tip> | ||
+ | **./gps coordonate.in avarii.in nume_destinatie coord_finale.out rezultat.out ** | ||
+ | </ | ||
+ | unde numele destinației reprezintă locația unde vrem să ajungem pornind din nodul pe care am zis că-l vom considera nod de plecare. | ||
- | < | + | În fișierul coord_finale.out se vor scrie numele și perechea (x,y) de coordonate calculate pentru fiecare locație, în ordinea citirii lor din fișierul de intrare coordonate.in |
- | <div class=" | + | |
- | <ul> | + | Având toate aceste date, vrem să calculăm care este cel mai scurt drum de la nodul de plecare, la cel destinație, |
+ | |||
+ | ===== Exemplu (date fictive momentan, nu e test real!!)===== | ||
+ | ^ coordonate.in ^ avarii.in | ||
+ | |5 | ||
+ | |dalas | ||
+ | |12 13 2 | ||
+ | |10 9 3 | ||
+ | |12 8 2 | ||
+ | |denver | ||
+ | |2 7 4 | ||
+ | |2 8 5 | ||
+ | |4 6 4 | ||
+ | |texas | ||
+ | |2 3 4 | ||
+ | |2 3 4 | ||
+ | |2 3 4 | ||
+ | |maryland | ||
+ | |2 3 4 | ||
+ | |2 3 4 | ||
+ | |2 3 4 | ||
+ | |ilinois | ||
+ | |2 3 4 | ||
+ | |2 3 4 | ||
+ | |2 3 4 | ||
+ | |||
+ | ===== Reguli pentru trimitere ===== | ||
+ | |||
+ | - Arhiva temei va avea numele // | ||
+ | - Ea va conține (direct în rădăcină): | ||
+ | * fișierul main.c | ||
+ | * Makefile-ul (cu regulile make pentru executabilul **gps** și clean) | ||
+ | * fișierul README în care va fi descrisă soluția problemei | ||
+ | - Dacă veți calcula coordonatele spațiale pentru toate locațiile (adică fișierul de ieșire coord_finale.out e integral corect pentru un test), se poate obține punctaj parțial de **50p** | ||
+ | - Dacă soluția voastră nu compilează, | ||
+ | - | ||
+ | |||
+ | ===== Referințe ===== | ||
+ | <html> | ||
< | < | ||
< | < | ||
- | </ul> | ||
- | </ | ||
</ | </ | ||