DRŽAVNO NATJECANJE 2013. – Drugi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 1. zadatak

Ante radi u poduzeću Antena d.o.o. te je dobio koncesiju da instalira antene mobilne mreže duž rijeke Nil u Egiptu.

Egipatska sela predstavljamo točkama u koordinatnoj ravnini tako da se rijeka Nil podudara sa osi x. Svaka antena ima doseg D, te će selo na koordinatama (X, Y) biti pokriveno signalom ako se nalazi unutar ili na rubu kruga radijusa D kojemu je neka antena u središtu.

Zbog nepristupačnog terena svaka se antena mora nalaziti na samoj rijeci Nil odnosno mora ležati na osi x.

Nadalje, sva sela će imati cjelobrojne koordinate te se svaka antena treba smjestiti na točku s cjelobrojnim koordinatama (dakle svaka antena A će imati koordinate (XA, 0) gdje je XA cijeli broj).

Napišete program koji na temelju lokacija egipatskih sela računa najmanji broj antena potreban da se sva sela pokriju signalom.

Test podaci će biti takvi da rješenje uvijek postoji.

Ulazni podaci

U prvom retku ulaza nalaze se dva prirodna broja N i D (1 ≤ N, D ≤ 100 000), broj sela i doseg jedne antene.

U sljedećih N redaka nalaze se po dva prirodna broja odvojena razmakom - koordinate odgovajućeg sela (0 < Xi, Yi ≤ 100 000, Yi ≤ D).

Izlazni podaci

U prvi i jedini redak izlaza potrebno je ispisati najmanji broj antena koje je potrebno postaviti tako da svako selo bude pokriveno signalom.

Primjeri test podataka

Ulaz

5 5
13 1
5 5
1 5
9 1
19 3

Izlaz

3

Ulaz

8 7
9 5
7 2
1 7
9 5
1 6
9 1
4 1
9 4

Izlaz

2