Fişierul intrare/ieşire:laser.in, laser.outSursăpreONI 2007, Runda 4
AutorAdrian Diaconu, Tiberiu-Lucian FloreaAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.15 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Laser

Gigel a terminat inca o zi de munca la magazinul tatalui sau. Acum nu mai trebuie decat sa stinga neoanele sa incuie vitrinele si poate pleca linistit acasa. Vom considera magazinul ca fiind planul de coordonate xOy. Neoanele vor fi date sub forma unor segmente in plan. Gigel se afla in punctul de coordonate (0,0) si dispune de o arma laser cu care poate trage in orice directie. In momentul in care Gigel trage cu laserul intr-o anumita directie toate neoanele care se intersecteaza cu semidreapta respectiva isi schimba starea(din inchise devin deschise si din deschise inchise).
Cunoscandu-se pozitia si starea initiala a neoanelor indicati-i lui Gigel in ce directii trebuie sa traga pentru a stinge toate neoanele. Se stie ca arma nu mai poate functiona dupa 10.000 de trageri deci trebuie o indicata o solutie cu numar mai mic sau egal de trageri.

Date de intrare

Prima linie a fisierului de intrare laser.in contine un numar natural N, numarul de neoane. Pe urmatoarele N linii se afla cate patru numere naturale x1 y1 x2 y2, punctele de coordonate (x1,y1) si (x2,y2) reprezentand capetele neoanelor. Pe ultima linie din fisier se afla N numere cu urmatoarea semnificatie: daca al i-lea numar este 1 atunci neonul i este aprins, altfel neonul este stins.

Date de iesire

Pe prima linie din fisierul de iesire laser.out se afla X, numarul de trageri. Pe urmatoarele X linii se va afla cate un numar reprezentand unghiul pe care directia in care se face a i-a tragere il face cu axa Ox.

Restrictii

  • Pentru a primi punctaj pe un anumit test trebuie ca X ≤ 10.000
  • 1 ≤ N ≤ 512
  • -10.000 ≤ x1,y1,x2,y2 ≤ 10.000
  • Coordonatele capetelor segmentelor vor fi numere intregi
  • Solutia nu este unica, dar exista mereu cel putin o solutie
  • Neoanele se pot intersecta intre ele
  • Nu vor exista doua capete ale neoanelor coliniare cu originea
  • Rezultatul va fi verificat cu o precizie de 0.00001 adica se va considera ca daca semidreapta care reprezinta directia in care trage Gigel va trece la distanta 0.00001 de neon acesta isi va schimba starea
  • Recomandare: afisati unghiurile cu 6 zecimale
  • Unghiurile in care se vor face tragerile vor fi exprimate in grade si vor fi din intervalul [0,360]

Exemplu

laser.inlaser.out
4
2 1 1 2
4 5 1 -3
3 -2 -3 -2
-1 3 -3 1
1 1 1 0
2
45.00000
270.0000

Explicatii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content