Prehod čez cesto

Osnovne informacije

Omejitve
  • Čas: 1 s
  • Spomin: 256 MB
Avtor:
  • Maks Kolman
  • UPM 2018

Pošlji rešitev



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

Janezek želi iti po sladoled na drugo stran N-pasovnice. Držite ga pred prvim pasom ceste po kateri vozijo različna vozila. Vsa vozila so pravokotne oblike, različnih dolžin in širine 10, kar je enako širini voznih pasov.

Za potrebe naloge potrebujemo še sledečo nerealistično predpostavko: Če vozila po istem pasu vozijo v različne smeri ali z različnimi hitrostmi, brez posledic zapeljejo skozi ovirajoča vozila. Za Janezka pa je usoden že dotik kateregakoli vozila.

Ko Janezka spustite, se bo začel plaziti čez cesto s konstantno hitrostjo 1. Premikal se bo samo v pravokotni smeri glede na prometne pasove in sicer bo vedno na koordinati X=0. Vozniki ne bodo spreminjali svoje hitrosti ali pasu, po katerem vozijo.

Naloga

Napišite program, ki bo izračunal, ob katerem času morate spustiti Janezka, da čimprej pride čez cesto in ga pri tem ne zbije nobeno od vozil.

Vhodni podatki

V prvi vrstici sta dve celi števili N in M, ki predstavljata število pasov ceste in število vozil na cesti.

Vsaka izmed naslednjih M vrstic opisuje vozilo na cesti (i-ta vrstica opisuje i-to vozilo). Vsaka vrstica vsebuje štiri števila P_i, X_i, V_i in D_i, ki imajo naslednji pomen:

  • P_i je številka pasu, po katerem vozilo vozi.
  • X_i je položaj sprednjega dela vozila ob času 0.
  • V_i je hitrost vozila (pozitivna predstavlja vožnjo v desno, negativna pa v levo).
  • D_i je dolžina vozila.

Omejitve vhodnih podatkov

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^3
  • 1 \leq P_i \leq N
  • 0 \leq |X_i| \leq 10^6
  • 1 \leq |V_i| \leq 10^6
  • 1 \leq D_i \leq 10^6

Izhodni podatki

Izpišite eno samo število – ob katerem času naj spustimo Janezka, da bo čim prej varno prišel čez cesto.

Rezultat šteje kot napačen, če se od uradnega razlikuje za več kot 10^{-6}.

Primeri

Vhod

2 2
1 -10 1 3
2 20 -2 10

Izhod

13.0

Vhod

1 1
1 -10 1 10

Izhod

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