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:
| 
2004-2016 BDG algoritmus szakkör