Gym-101915J The Volcano Eruption 计算几何

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

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

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

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

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

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

 #include<bits/stdc++.h>

 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]))<sqr(r[a]+r[b]+eps) );

 }

 void dfs(int u)

 {

     if (vis[u]) return ;

     vis[u]=;

     if (x[u]+r[u]>=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);

     }

 }

巴特西

Gym-101915J The Volcano Eruption 计算几何

最新文章

热门文章