Solução por Pedro Racchetti
Materiais prévios necessários:
Para esse problema, usaremos alguns conceitos de geometria computacional, e um algoritmo de achar componentes conexas em grafos (nessa solução usarei Union-Find). Primeiramente, é preciso perceber que dois círculos se intersectam se e somente se a soma dos raios for no máximo, a distância entre os centros. Mais formalmente, existe intersecção entre dois círculos $$i$$ e $$j$$ se e somente se $$r_i + r_j$$ $$\leq$$ $$d(centro_i, centro_j)$$, sendo $$d(x, y)$$ a distância entre os pontos $$x$$ e $$y$$.
Como o total de buracos é menor que 1000, podemos montar um grafo em $$O(n^2)$$ da seguinte maneira: os vértices serão os buracos, e para cada buraco, criaremos uma aresta entre ele e todos os buracos que fazem intersecção com ele, desse modo, as intersecções de buracos serão as componentes conexas. É fácil ver que o ponto mais a esquerda de um buraco $$i$$ é $$(x_i – r_i, y_i)$$ e o ponto mais a direita desse buraco $$(x_i + r_i, y_i)$$, podemos portanto guardar, para cada componente conexa, o ponto mais a esquerda e o ponto mais a direita dos buracos contidos nela, chamaremos esses pontos de $$maxesq$$ e $$maxdir$$. Então, para cada componente em que a coordenada $$x$$ de $$maxesq$$ é $$\leq 0$$ e a coordenada $$x$$ de $$maxdir$$ é $$\geq W$$ , Bernardo terá de usar uma roupa especial. A imagem da esquerda mostra o grafo que representaria a situação (feita no csacademy) e a da direita explica uma possível solução para o caso no problema (ela está no problema original):
Segue o código comentado para melhor compreensão da solução:
| #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); | |
| } | |
| } |


