Solução Informática - Nível Avançado - Semana 1

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);
}
}