Gusarji

Osnovne informacije

Omejitve
  • Čas: 2 s
  • Spomin: 256 MB
Avtor:
  • Janez Brank
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Kapitan cindžnoro vzame,
v podpalubje pohiti,
s fajercajgom pulfer vname,
z ladjo vred v luft zleti.
Heja bumbarasa, heja bumbarasa!
― Frane Milčinski – Ježek, Gusarska

Na morju pri miru stoji ladja, ki se ji iz več smeri bližajo gusarski čolni. Vsega skupaj je n čolnov, pri čemer se i-ti od njih na začetku dogajanja nahaja v smeri b_i glede na ladjo in na oddaljenosti d_i milj od nje, ladji pa se približuje s konstantno hitrostjo v_i milj na uro. (Smeri se merijo v stopinjah: 0 pomeni sever, 45 severozahod, 90 zahod itd.)

Ladja ima za obrambo pred gusarji laserski žarek – to je neskončno dolg poltrak, ki izhaja iz ladje in v hipu potopi vsak čoln, ki se ga dotakne (za potrebe te naloge predpostavimo, da so čolni točkasti in da se ves čas premikajo naravnost proti ladji). Žarek je na začetku dogajanja usmerjen v smer a, posadka ladje pa ga lahko vrti v poljubno smer (levo ali desno) s kotno hitrostjo največ w obratov na minuto.

Naloga

Napišite program, ki prebere podatke o ladji in čolnih ter ugotovi, ali je mogoče z žarkom potopiti vse gusarske čolne, ne da bi se kateri približal ladji na manj kot 1 miljo. Če je to mogoče, mora vaš program tudi izračunati najmanjši čas (od začetka dogajanja), v katerem je mogoče tako potopiti vse čolne.

Vhodni podatki

V prvi vrstici so števila a, w in n. Sledi n vrstic, pri čemer i-ta od njih vsebuje števila b_i, d_i in v_i.

Omejitve vhodnih podatkov

  • Število n je naravno število, za katero velja 1 \le n \le 500.
  • 0 \le a < 360
  • 0{,}01 \le w \le 1
  • 0 \le b_i < 360
  • 1 \le d_i \le 1000
  • 0{,}01 \le v_i \le 100
  • Števila a, w, b_i, d_i, v_i so realna števila in so podana na največ tri decimalke.
  • Vsi b_i so med seboj različni in so tudi različni od a.

Opomba glede računske natančnosti: Testni podatki so takšni, da se pravilen rezultat ne spremeni, tudi če pustimo gusarskim ladjam, da se približajo na 1 \pm 0{,}0001 milje.

Izhodni podatki

Če ni mogoče potopiti vseh čolnov, ne da bi se kateri približal ladji na manj kot 1 miljo, izpišite -1, sicer pa izpišite najkrajši čas (v minutah od začetka dogajanja), v katerem je mogoče potopiti vse čolne (ne da bi se kdaj kateri približal ladji na manj kot eno miljo). Vrednost, ki jo izpišete, sme za največ 0{,}001 odstopati od pravega rezultata.

Primeri

Vhod

0.0 0.06 2
140.0 22.0 100.0
210.0 22.0 100.0

Izhod

9.7222222

Vhod

10.0 0.06 2
140.0 15.0 100.0
210.0 15.0 100.0

Izhod

-1
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task