题意:给你一个矩阵,然后有很多的圆,这些圆可能相交着,一个或者几个就导致这个矩形被分割开了,就是从最下面的边到上面的边,连线被这些圆阻隔了,每一堆圆当做一个阻碍,问一共有几个阻碍
题解:看起来好难做啊!~!,我怎么知道一堆圆就把矩阵一横着的局域都占完了
哎然后猛然发现,相交的2个圆,是不是可以连边,
然后从对于每个联通的子图,是不是最左边的圆上有点超过了矩形最左边,同时右边也是,就隔开了!
所以建图(实际这个图也不用建出来),dfs一下就行了
注意一下精度的问题,所有比大小相关的最后都带eps
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 1005 4 #define eps 1e-6 5 double w,l,x[N],y[N],r[N],ll,rr; 6 int cnt,T,n,vis[N],ok=1; 7 double sqr(double x){return x*x;} 8 int check(int a,int b) 9 { 10 return ( (sqr(x[a]-x[b])+sqr(y[a]-y[b]))<sqr(r[a]+r[b]+eps) ); 11 } 12 void dfs(int u) 13 { 14 if (vis[u]) return ; 15 vis[u]=1; 16 if (x[u]+r[u]>=w) ok=0; 17 for (int v=0;v<n;v++) 18 { 19 if (v==u) continue; 20 if (!vis[v] && check(u,v)) dfs(v); 21 } 22 return ; 23 } 24 int main() 25 { 26 scanf("%d",&T); 27 while (T--) 28 { 29 scanf("%d%lf%lf",&n,&w,&l); 30 cnt=0; 31 memset(vis,0,sizeof(vis)); 32 for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&x[i],&y[i],&r[i]); 33 for (int i=1;i<=n;i++) 34 if (x[i]-r[i]<=eps) 35 { 36 ok=1; 37 if (!vis[i]) dfs(i); 38 if (ok==0) cnt++; 39 40 } 41 printf("%d ",cnt); 42 } 43 }