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:
https://gist.github.com/PedroRacchetti/3dbd05ba3541537a82587c403d26e6db