Fruit Ninja

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Avtor:
  • Tomaž Hočevar
  • UPM 2018

Pošlji rešitev



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

Cilj igre Fruit Ninja je prerezati čim več premikajočega sadja s posameznimi potegi z rezilom. Ključna komponenta implementacije je algoritem, ki ugotovi, katero sadje je igralec prerezal z nekim potegom. Pri tej nalogi se bomo posvetili poenostavljeni različici tega problema.

Podanih je N različno velikih statičnih krogov, ki ponazarjajo sadje. Središče i-tega kroga je v točki (P_i, Q_i), njegov polmer pa je R_i. Napišite program, ki bo izračunal, koliko krogov seka ali pa se jih dotika daljica od točke A = (X_A, Y_A) do točke B = (X_B, Y_B).

Zagotovljeno je, da igralec ne bo nikoli za las zgrešil sadja, tj. z rezom se ga bo bodisi dotaknil oz. ga presekal ali pa mu to ne bi uspelo, tudi če bi bil premer sadja za 0.0001 večji.

Vhodni podatki

V prvi vrstici se nahajajo števila X_A, Y_A, X_B, Y_B. V naslednji vrstici je podano število krogov N, ki ponazarjajo sadje. Podani so v naslednjih N vrsticah s parametri P_i, Q_i in R_i. Vsi vhodni podatki so cela števila.

Omejitve vhodnih podatkov

  • Koordinate in polmeri po absolutni vrednosti ne presežejo 1000.
  • 1 \leq N \leq 1000
  • 0 < R_i

Izhodni podatki

Izpišite, koliko sadja preseka (oz. se dotakne) poteg z rezilom od točke A do točke B.

Primeri

Vhod

0 -1 4 1
5
0 0 1
2 -1 1
5 1 1
-1 -2 1
5 -2 2

Izhod

3

Vhod

3 1 3 6
6
5 2 2
3 7 1
3 -2 1
1 3 1
4 5 3
1 1 100

Izhod

4

Komentar

Slika prikazuje prvi primer, kjer s potegom rezila uspešno zarežemo v prve tri sadeže.

Prvi primer

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