【BZOJ1043】[HAOI2008]下落的圆盘 几何

【BZOJ1043】[HAOI2008]下落的圆盘

Description

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

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

题解：对于每个圆，我们枚举它后面的所有圆，先判断后面的圆是否完全覆盖了当前圆，再考虑相交的情况。我们求出后面的圆覆盖了当前圆的哪部分，然后我们将圆的周长拉直，那么每个被覆盖的部分都可以看成一个线段，求一下这些线段的并即可。

求圆交方法：直接用余弦定理求出覆盖角度的大小，然后用极角求出角的位置即可。如果角的大小>=2pi或<0，则需要特殊处理。

求线段并方法：我的方法可能有点naive，方法是将线段左端看成+1，右端看成-1，那么排个序求前缀和，前缀和>0的部分就是被覆盖的部分。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define pi acos(-1.0)
using namespace std;
struct circle
{
double x,y,r;
circle(){}
circle(double a,double b){x=a,y=b;}
circle operator + (circle a){return circle(x+a.x,y+a.y);}
circle operator - (circle a){return circle(x-a.x,y-a.y);}
circle operator * (double a){return circle(x*a,y*a);}
circle operator / (double a){return circle(x/a,y/a);}
}c[1010];
struct node
{
double x;
int v;
}p[2010];
double ans;
double dist(circle a,circle b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
int n,tot,sum,flag;
bool cmp(node a,node b)
{
return a.x<b.x;
}
int main()
{
scanf("%d",&n);
int i,j;
for(i=1;i<=n;i++)scanf("%lf%lf%lf",&c[i].r,&c[i].x,&c[i].y);
for(i=1;i<=n;i++)
{
tot=sum=flag=0;
for(j=i+1;j<=n;j++)
{
double dis=dist(c[i],c[j]);
if(dis<=c[j].r-c[i].r)
{
flag=1;
break;
}
if(dis>fabs(c[i].r-c[j].r)&&dis<=c[i].r+c[j].r)
{
double a=acos((c[i].r*c[i].r+dis*dis-c[j].r*c[j].r)/(2*c[i].r*dis));
double b=atan2(c[j].y-c[i].y,c[j].x-c[i].x);
p[++tot].x=b-a,p[tot].v=1,p[++tot].x=b+a,p[tot].v=-1;
if(p[tot-1].x<0)p[tot-1].x+=2*pi;
if(p[tot].x<0)p[tot].x+=2*pi;
if(p[tot-1].x>=2*pi)p[tot-1].x-=2*pi;
if(p[tot].x>=2*pi)p[tot].x-=2*pi;
if(p[tot-1].x>p[tot].x)sum++;
}
}
if(flag)continue;
ans+=c[i].r*2*pi;
if(!tot)continue;
sort(p+1,p+tot+1,cmp);
for(j=1;j<=tot;j++)
{
if(sum)ans-=c[i].r*(p[j].x-p[j-1].x);
sum+=p[j].v;
}
if(sum)ans-=c[i].r*(2*pi-p[tot].x);
}
printf("%.3lf",ans);
return 0;
}