Programozás‎ > ‎Feladatok‎ > ‎

Aknák

Egy aknamezőt kell megtisztítani az aknáktól. Bizonyos aknákra időzítőt szerelhetünk és távolról felrobbanthatjuk őket. Ha egy akna felrobban, akkor egy adott sugarú körben a detonáció további aknákat robbanthat be, így láncreakció indulhat el. Mivel az aknák bütykölése  veszélyes, szeretnénk a lehető legkevesebb akna berobbantásával megsemmisíteni az összes aknát.

Feladat

Írjunk programot, ami megadja, hogy minimálisan hány akna felrobbantásával lehet a terepet megtisztítani, és meg is adja, hogy melyek ezek az aknák.

Bemenet

A bemenet első sora az aknák N számát adja meg (1<= N <= 100000). Ezután N sorban az aknák leírása következik:

X[0] Y[0] R[0]
X[1] Y[1] R[1]
...
X[N-1] Y[N-1] R[N-1]

A koordináták és a detonációs sugár is egész szám. Ha két akna távolsága pont egyenlő a detonációs sugárral, az még elég arra, hogy a második akna is felrobbanjon.

Kimenet

Egyetlen sorba a minimális számú felrobbantásra jelölt akna indexét kell írni, szóközökkel elválasztva.

Példa

Bemenet  Kimenet
5
-15 4 10
12 4 8
-10 -4 8
2 10 16
18 10 8
0 3


Tesztadatok

Címkék

A feladat forrása: BME 24-órás programozó verseny, 2012 EC
Algoritmusok: