volcanoeruption.cpp

 #include<bits/stdc++.h>
using namespace std;

const int MAXN = 1123;

struct circulo{ //essa struct representara os buracos

	double raio, x, y;


};
circulo cs[MAXN];

struct intersec{
	//essa struct representa as componentes conexas
	double maxesq, maxdir;


};
intersec is[MAXN];



double dist(circulo c1, circulo c2){
	//essa função retorna a distancia euclidiana entre os centros de dois circulos,
	//pelo teorema de pitágoras
	double dy = (c1.y - c2.y);
	dy *= dy;
	double dx = (c1.x - c2.x);
	dx *= dx;

	return sqrt(dx + dy); 

}

//Aqui, encontramos o representante da componente conexa a qual
// um vertice pertence, com o algoritmo de Union-Find

int pai[MAXN], prof[MAXN];
int find(int a){
    if(pai[a] == a) return a;
    return pai[a] = find(pai[a]);
}

//Adicionamos uma aresta entre os buracos a e b, com o algoritmo 
//de Union-Find

void join(int a, int b){
    a = find(a);
    b = find(b);
    if(prof[a] > prof[b]){
        prof[b] = prof[a];
        pai[b] = a;
    }
    else if(prof[a] < prof[b]){
        prof[a] = prof[b];
        pai[a] = b;
    }
    else{
        prof[a] += 1;
        pai[b] = a;
    }
}

int n;
double w, l;
map<int, int> componentes; //mapeamos o pai de cada componente a um numero
int totcomponentes; //guardamos o total de componentes conexas


int main(){
	//lemos a quantidade de casos de teste
	int t;
	scanf("%d", &t);
	while(t--){
		totcomponentes = 0;
		scanf("%d %lf %lf", &n, &w, &l);
		for(int i = 0; i < n; i++){
			//lemos a entrada e inicializamos os vetores
			scanf("%lf %lf %lf", &cs[i].x, &cs[i].y, &cs[i].raio);
			componentes[i] = -1;
			pai[i] = i;
			prof[i] = 0;
		}
		//encontramos as interseccoes, e criamos arestas entre os circulos
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(find(i) != find(j) &&  dist(cs[i], cs[j]) <= cs[i].raio + cs[j].raio){
					join(find(i), find(j));
				}
			}
		}

		//fazemos o mapeamento de cada componente, caso ainda nao tenha sido feito
		for(int i = 0; i < n; i++){
			if(componentes[find(i)] == -1){
				componentes[find(i)] = totcomponentes++;
				is[componentes[find(i)]].maxesq = cs[i].x - cs[i].raio;
				is[componentes[find(i)]].maxdir = cs[i].x + cs[i].raio;
			}
			// encontramos o maxdir e maxesq de cada componente
			is[componentes[find(i)]].maxesq = min(is[componentes[find(i)]].maxesq, cs[i].x - cs[i].raio);
			is[componentes[find(i)]].maxdir = max(is[componentes[find(i)]].maxdir, cs[i].x + cs[i].raio);
		}

		int ans = 0;
		for(int i = 0; i < totcomponentes; i++){

			if(is[i].maxesq <= 0 && is[i].maxdir >= w ){
				//sempre que uma componente cobrir toda a rua, incrementamos a resposta
				ans++;
			}
		}
		printf("%d\n", ans);


	}


}