[HAOI2008]下落的圆盘

时间：2021-03-17 12:58:08

Description

　　有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红
色线条的总长度即为所求. [HAOI2008]下落的圆盘

Input

　　第一行为1个整数n,N<=1000
接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.

Output

　　最后的周长，保留三位小数

Sample Input

2
1 0 0
1 1 0

Sample Output

10.472
枚举每一个圆，看它有多少没有被覆盖。
每一个圆的极角可以拉直成一个长为2×pi的线段
然后套用数学公式，算出一个圆覆盖的范围
要注意讨论极角小于0的情况
 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 struct ZYYS

 {

   double l,r;

 }a[];

 double pi=acos(-1.0);

 int n;

 double x[],y[],r[],ans;

 bool cmp(ZYYS a,ZYYS b)

 {

   return a.l<b.l;

 }

 double dist(int i,int j)

 {

   return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

 }

 bool contain(int i,int j)

 {

   if (r[i]-r[j]>=dist(i,j)) return ;

   return ;

 }

 double cal(int o)

 {int i;

   int cnt=;

   for (i=o+;i<=n;i++)

     if (contain(i,o)) return ;

   for (i=o+;i<=n;i++)

     {

       if (contain(o,i)||dist(o,i)>=r[i]+r[o]) continue;

       double d=dist(o,i);

       double xt=acos((-r[i]*r[i]+r[o]*r[o]+d*d)/(2.0*d*r[o]));

       double aef=atan2(y[i]-y[o],x[i]-x[o]);

       a[++cnt]=(ZYYS){aef-xt,aef+xt};

       if (a[cnt].l<) a[cnt].l+=*pi;

       if (a[cnt].r<) a[cnt].r+=*pi;

       if (a[cnt].l>a[cnt].r)

     {

       double p=a[cnt].l;

       a[cnt].l=;

       a[++cnt].l=p;a[cnt].r=*pi;

     }

     }

   sort(a+,a+cnt+,cmp);

   double res=,now=;

   for (i=;i<=cnt;i++)

     {

       if (a[i].l>now) res+=a[i].l-now,now=a[i].r;

       now=max(now,a[i].r);

     }

   res+=*pi-now;

   return res*r[o];

 }

 int main()

 {int i;

   cin>>n;

   for (i=;i<=n;i++)

     {

       scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);

     }

   for (i=;i<=n-;i++)

     ans+=cal(i);

   ans+=*pi*r[n];

   printf("%.3lf\n",ans);

 }

相关文章