Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

--- teme:tema2 [2017/02/15 21:08]
florina_elena.barbu
+++ teme:tema2 [2017/04/26 18:04] (curent)
iulian.matesica
@@ Linia 2: / Linia 2: @@
-==== Obiective ====
+===== Obiective =====
     * Înțelegerea conceptului de graf și a modurilor de parcurgere aferente
     * Aplicarea algoritmilor studiați pe topologie graf într-un exemplu practic
+===== Informații =====
+  * Deadline soft, **26 aprilie ora 23:59**
+  * Termen final de trimitere **4 mai ora 23:59** (depunctare de 0.5pt/zi, maxim 4p depunctare).
+  * Trimiterea temelor se face pe platforma [[https://vmchecker.cs.pub.ro/ui/#SDAAB|vmchecker]] (folosiți credențialele de pe acs.curs.pub.ro).
-==== Descriere ====
+===== 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.
@@ Linia 27: / Linia 33: @@
-==== Precizări ====
+===== 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.
+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:
@@ Linia 40: / Linia 46: @@
   *   raza R satelit3
+ \\
-Coordonatele și raza se consideră date de fiecare satelit pentru fiecare dintre cele N locații.
+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, obținându-le prin găsirea triadelor (x,y,z) care să satisfacă ecuațiile sferei.
@@ Linia 47: / Linia 53: @@
 <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ă)
+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; fiecare locație va fi considerată ca fiind un nod al grafului prin care ne construim drumurile de la o locație la alta.
+</note>
+<note tip>
+Dacă cei 3 sateliţi sunt reprezentaţi cu cercurile C1(x1, y1, R1), C2(x2, y2, R2) şi C3(x3, y3, R3), atunci punctul de intersecţie al celor 3 cercuri, P(x, y) va respecta ecuaţiile:
+**(x-x1)<sup>2</sup> + (y-y1)<sup>2</sup> = R1<sup>2</sup>**
+**(x-x2)<sup>2</sup> + (y-y2)<sup>2</sup> = R2<sup>2</sup>**
+**(x-x3)<sup>2</sup> + (y-y3)<sup>2</sup> = R3<sup>2</sup>**
 </note>
@@ Linia 53: / Linia 70: @@
 Știind coordonatele tuturor locațiilor, vom considera costul de la o locație la cealaltă distanța dintre cele 2 puncte în plan.
+<note tip>
+Pentru punctele P1(x1, y1) şi P2(x2, y2) putem scrie ecuaţia distanţei: P1P2 = dist(P1,P2) = **sqrt( (x1-x2)<sup>2</sup> + (y1-y2)<sup>2</sup> )**
+</note>
-Vom primi un update printr-un fișier //avarii.in// drumurile avariate dintre 2 locații, pe care nu se poate merge.
+Vom primi un update printr-un fișier //avarii.in// drumurile avariate dintre 2 locații, pe care **nu** se poate merge.
-==== Cerințe ====
+===== Cerințe =====
 Executabilul obținut în urma compilării va avea numele **//gps//**, iar regula de execuție va fi:
-<file cpp>
+<note tip>
-./gps coordonate.in avarii.in nume_destinatie
+**./gps coordonate.in avarii.in nume_destinatie coord_finale.out rezultat.out **
-</file>
+</note>
-unde numele destinației reprezintă locația unde vrem să ajungem.
+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.
-Având toate aceste date, vrem să calculăm care este cel mai scurt drum de la nodul de plecare, la cel destinație.
+Î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
+Având toate aceste date, vrem să calculăm **costul** celui mai scurt drum de la nodul de plecare, la cel destinație, pe care îl vom scrie în fișierul //rezultat.out// .
-==== Reguli pentru trimitere ====
+===== Exemplu (date fictive momentan, nu e test real!!)=====
+^ coordonate.in ^       avarii.in   ^     coord_finale.out ^ rezultat.out ^
+|8                    |Loctie8 Locatie5 |19 17             |5             |
+|Locatie1             |Loctie6 Locatie8 |18 17             |              |
+|Satelit0 51 41 40    |Loctie3 Locatie1 |0 6               |              |
+|Satelit1 54 5 37     |                 |16 7              |              |
+|Satelit2 376 93 365  |                 |13 10             |              |
+|                     |                 |10 19
+|Locatie2             |                 |17 3              |              |
+|Satelit0 158 65 148  |                 |18 15             |              |
+|Satelit1 51 561 545  |                 |                  |              |
+|Satelit1 51 561 545  |                 |                  |              |
+|                     |                 |                  |              |
+|Locatie3             |                 |                  |              |
+|Satelit0 289 6 289   |                 |                  |              |
+|Satelit1 264 176 314 |                 |                  |              |
+|Satelit2 217 462 505 |                 |                  |              |
+|                     |
+|Locatie4             |                 |                  |              |
+|Satelit0 9 31 25     |                 |                  |
+|Satelit1 16 39 32    |                 |                  |              |
+|Satelit2 208 263 320 |                 |                  |              |
+|
+|Locatie5             |
+|Satelit0 205 66 200  |
+|Satelit1 76 26 65    |
+|Satelit2 266 214 325 |
+|
+|Locatie6 |
+|Satelit0 322 285 410|
+|Satelit1 82 173 170|
+|Satelit2 175 551 557|
+|
+|Locatie7|
+|Satelit0 53 3 36|
+|Satelit1 137 25 122|
+|Satelit2 52 615 613|
+|
+|Locatie8|
+|Satelit0 70 351 340|
+|Satelit1 379 15 361|
+|Satelit2 87 275 269|
+===== 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 </br>
+    * fișierul main.c </br>
-  * Makefile-ul (cu regulile make pentru executabilul **gps** și clean)
+    * Makefile-ul (cu regulile make pentru executabilul **gps** și clean)
-  * fișierul README în care va fi descrisă soluția problemei
+    * 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ă 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ă, 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 =====
-==== Referințe ====
 <html>
  <li class="level1"><div class="li"><a class="urlextern" href = "http://www.physics.org/article-questions.asp?id=55">How does GPS work? </a></div></li>

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină