Državno natjecanje 2018. godine za 3. i 4. razred Srednje Škole - 1. zadatak - Dan 2

Mlada Marija pojavila se na igralištu svoje nove škole. Škola je sav novac potrošila na uređenje igrališta, a ne na opremu za igranje, pa tako svi učenici, uključujući i Mariju, igraju zamišljenu igru nazvanu kugloboćanje u svojim glavama.

U igri jedna osoba, u ovom slučaju Marija, igra protiv ostalih N učenika. Svaki učenik zamisli jednu kružnicu (čunj) sa središtem (Xi, Yi) te proizvoljnim radijusom Ri u koordinatnom sustavu, tako da se potpuno nalazi u prvom i drugom kvadrantu, tj. sve točke kružnice nalaze se iznad x-osi ili leže na njoj.

Nakon toga Marija nekoliko puta “baca” zamišljenu kružnicu (kuglu) fiksnog radijusa R iz središta koordinatnog sustava u nekom smjeru prema beskonačnosti. Svaki put kad ona “baci” tu kružnicu, neki od čunjeva ispadaju iz igre iz razloga što ih je kružnica koju je Marija bacila dotaknula, tj. te dvije kružnice imale su presjek u nekom trenutku putovanja Marijine kružnice prema beskonačnosti.

Budući da je Marija nova na školskom igralištu i želi se dokazati, pomozite joj odgovoriti na pitanje koji je najmanji broj kugli koje ona mora “baciti” kako bi uspješno izbacila sve ostale učenike (tj. njihove čunjeve) iz igre.

ULAZNI PODACI

U prvom retku nalaze se dva broja, prirodan broj N i realan broj R s preciznošću od dvije decimale (1 ≤ N ≤ 100 000, 0 ≤ R ≤ 1000), broj učenika i radijus Marijine kružnice.

U sljedećih N redaka nalaze se po dva cijela broja Xi i Yi te realan broj Ri s preciznošću od dvije decimale (-1000 ≤ Xi ≤ 1000, 0 ≤ Yi ≤ 1000, 0 ≤ Ri ≤ Yi), koordinate središta kružnice učenika i radijus te kružnice.

Ako je R = 0, Marijina kružnica zapravo je točka. Ako je Ri= 0, kružnica učenika zapravo je točka.

IZLAZNI PODACI

U jedini redak ispišite traženi najmanji broj “bacanja” kružnice iz ishodišta (kugle) na kružnice učenika (čunjeve).

PRIMJERI TEST PODATAKA

ulaz

2 1.00
5 5 1.00
-5 5 1.00

izlaz

2

ulaz

3 0.10
1 1 0.10
2 2 0.10
3 3 0.10

izlaz

1

ulaz

2 1.00
1 6 1.00
5 4 2.00

izlaz

1

Objašnjenje

Pojašnjenje trećeg primjera: Skica u zadatku predstavlja jedno od mogućih bacanja kugle koja “pogađa” čunjeve tako da jedan čunj dodiruje, a s drugim ima presjek.