题面

题意:给你一个矩阵,然后有很多的圆,这些圆可能相交着,一个或者几个就导致这个矩形被分割开了,就是从最下面的边到上面的边,连线被这些圆阻隔了,每一堆圆当做一个阻碍,问一共有几个阻碍

题解:看起来好难做啊!~!,我怎么知道一堆圆就把矩阵一横着的局域都占完了

哎然后猛然发现,相交的2个圆,是不是可以连边,

然后从对于每个联通的子图,是不是最左边的圆上有点超过了矩形最左边,同时右边也是,就隔开了!

所以建图(实际这个图也不用建出来),dfs一下就行了

注意一下精度的问题,所有比大小相关的最后都带eps

#include
using namespace std;
#define N 1005
#define eps 1e-6
double w,l,x[N],y[N],r[N],ll,rr;
int cnt,T,n,vis[N],ok=;
double sqr(double x){return x*x;}
int check(int a,int b)
{
return ( (sqr(x[a]-x[b])+sqr(y[a]-y[b]))=w) ok=;
for (int v=;v<n;v++)
{
if (v==u) continue;
if (!vis[v] && check(u,v)) dfs(v);
}
return ;
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%lf%lf",&n,&w,&l);
cnt=;
memset(vis,,sizeof(vis));
for (int i=;i<=n;i++) scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
for (int i=;i<=n;i++)
if (x[i]-r[i]<=eps)
{
ok=;
if (!vis[i]) dfs(i);
if (ok==) cnt++;

         }  
     printf("%d\\n",cnt);  
 }  

}