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
În această problemă vom aplica un procedeu decent de a desena o stea pe un cerc suport, după cum urmează: trasăm o rază verticală în sus, apoi una în jos, apoi raze orizontale la 90 de grade de primele, apoi raze oblice la 45 de grade... şi aşa mai departe. La fiecare pas, trasăm o rază care partiţionează arcul de unghi maxim în două arce de unghiuri egale. Prin acest procedeu simplu, putem desena stele care să fie acceptabil de simetrice. Putem, deci, aplica procedeul pentru orice mulţime iniţială de raze.
Date de intrare
Pe prima linie a fişierului dstar.in se găseşte numărul R de raze, urmat de numărul P de partiţionări necesare până steaua arată acceptabil de simetric. Pe următoarele R linii se găsesc unghiurile dintre fiecare rază şi raza (imaginară) în sus, exprimate în grade.
Date de ieşire
Fişierul dstar.out conţine două linii, cu unghiurile cel mai mic şi cel mai mare dintre raze, dupa ce s-a aplicat procedeul.
Restricţii
- 1 ≤ R, P ≤ 1.000.000.
- Soluţiile 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
În primul exemplu, steaua conţine la început doar o singură (primul 1) rază în sus (unghiul de 0 grade). Apoi realizăm o singură partiţie (al doilea 1) cu o rază la unghiul de 180 de grade. S-au format două arce, de 180 de grade fiecare.
În al doilea exemplu, steaua conţine la început două raze (primul 2), situate la 90 şi 180 de grade de raza (imaginară) în sus. Realizăm două partiţii (al doilea 2). Prima partiţie se realizează în arcul de 270 grade, iar a doua în unul din arcele de 135 grade. Rezultă un arc de unghi minim de 67.5 de grade şi un arc de unghi maxim de 135 grade.
