Unelte utilizator
Bara de navigare
Aceasta e o versiune anterioară a paginii.
Tema 2: GPS tracker
Obiective
- Înțelegerea conceptului de graf și a modurilor de parcurgere aferente
- Aplicarea algoritmilor studiați pe topologie graf într-un exemplu practic
Descriere
Sistemul Global de Poziționare (sau GPS) este o rețea de aproximativ 30 de sateliți care orbitează în jurul Pământului, la o altitudine de 20.000km. 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.
Oriunde te afli pe planetă, cel puțin 3 sateliți sunt 'vizibili' la un moment dat. Fiecare transmite informații despre poziția sa și timpul curent la anumite intervale. Aceste semnale sunt interceptate de dispozitivul GPS care calculează cât de departe e satelitul, în funcție de cât de mult îi ia mesajului să ajungă.
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, nu a unghiurilor)
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.
Precizări
Vom considera ca fișier de intrare coordonate.in , în care pe prima linie vom avea un număr N care va reprezenta câte locații depistează sateliții noștri.
Pe următoarele linii vom avea pentru fiecare locație:
- nume locație
- coordonate (x1, y1, z) satelit1
- raza R satelit1
- coordonate (x2, y2, z) satelit2
- raza R satelit2
- coordonate (x3, y3, z) satelit3
- raza R satelit3
:!:<html>Alegerea trebuie să vă permită să ajungeți la o formulă de tipul r<sub>1</sub><sup>2</sup> - r<sub>2</sub><sup>2</sup> = 2*x<sub>relativ</sub>*x<sub>s2</sub> - x<sub>s2</sub><sup>2</sup>, x<sub>s2</sub>=coord x a satelitului2 în noul sistem. </br></br> Se consideră prima coordonată calculată, locul din care plecăm.</p>
<p>
Știind coordonatele tuturor locațiilor, vom considera costul de la o locație la cealaltă distanța dintre cele 2 puncte în plan. </p>
<p>
Vom primi un update printr-un fișier <i>avarii.in</i> drumurile avariate dintre 2 locații, pe care nu se poate merge.
</p>
<h2>Cerințe</h2> <p>
Executabilul obținut în urma compilării va avea numele <b><i> gps</i></b>, iar regula de execuție va fi: </br>
</html>
<file cpp> ./gps coordonate.in avarii.in nume_destinatie </file>
unde numele destinației reprezintă locația unde vrem să ajungem. Având toate aceste date, vrem să calculăm care este cel mai scurt drum de la nodul de plecare, la cel destinație.
Reguli pentru trimitere
- Arhiva temei va avea numele GrupaSerie_Nume_Prenume_TemaNr.zip și va fi încărcată pe vmchecker unde vă puteți loga folosind credențialele de pe acs.curs
- 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, se poate obține punctaj parțial de 50p
- Dacă soluția voastră nu compilează, dar dacă ideea este bună și trimiteți o încercare de implementare, puteți primi până la 20p
- Temele care vor fi copiate vor primi 0p
Referințe
