Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dstar.in, dstar.out | Sursă | ONIS 2015, Runda 2 |
| Autor | Vlad Manea | Adăugată de |  Vlad Manea •vlad.manea |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Desenand Stele
In aceasta problema vom implementa un procedeu decent de a desena stele. O stea poate fi desenata pe un cerc suport, dupa cum urmeaza: trasam o raza verticala in sus, apoi una in jos, apoi raze orizontale la 90 de grade de primele, apoi raze oblice la 45 de grade… si asa mai departe. La fiecare pas, trasam o raza care partitioneaza arcul de unghi maxim in doua arce de unghiuri egale. Prin acest procedeu simplu, putem desena stele care sa fie acceptabil de simetrice. Putem, deci, aplica procedeul pentru orice multime initiala de raze.
Date de intrare
Pe prima linie a fisierului dstar.in se gaseste numarul R de raze, urmat de numarul P de partitionari necesare pana steaua arata cat de cat simetric. Pe urmatoarele R linii se gasesc unghiurile exprimate in grade si in sens orar, dintre fiecare raza si raza (imaginara) in sus.
Date de ieşire
Fisierul dstar.out contine doua linii, cu unghiurile cel mai mic si cel mai mare dintre raze, dupa ce s-a aplicat procedeul de partitionare.
Restricţii
- 1 ≤ R, P ≤ 1.000.000.
- Solutiile pot avea o eroare de +/- 0.000001.
Exemple
| dstar.in | dstar.out |
|---|---|
| 1 1 0 | 180 180 |
| 2 2 90 180 | 67.5 135 |
Explicaţie
In primul exemplu, steaua contine la inceput doar o singura (primul 1) raza in sus (unghiul de 0 grade). Apoi realizam o singura partitie (al doilea 1) cu o raza la unghiul de 180 de grade. S-au format doua arce, de 180 de grade fiecare.
In al doilea exemplu, steaua contine la inceput doua raze (primul 2), situate la 90 si 180 de grade de raza (imaginara) in sus. Realizam doua partitii (al doilea 2). Prima partitie se realizeaza in arcul de 270 grade, iar a doua in unul din arcele de 135 grade. Rezulta un arc de unghi minim de 67.5 de grade si un arc de unghi maxim de 135 grade.
