【HAOI2008】bzoj1043 下落的圆盘

本文主要是介绍【HAOI2008】bzoj1043 下落的圆盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

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

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

Output

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

可以算是【uva1308 Viva Confetti】的升级版。
这回不能 $O(n^3)$ 枚举判断每一段小圆弧是否被覆盖了，可以把一个圆和在他上面的圆交出的所有圆弧找出来，找到这些弧的并集的补集就是这个圆露出的部分。求并集的时候可以转化为序列上的问题，做法就很多了。

#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const double eps=1e-8,pi=acos(-1);
int dcmp(double x)
{if (x>eps) return 1;if (fabs(x)<eps) return 0;return -1;
}
struct Vector
{double x,y;void rd(){scanf("%lf%lf",&x,&y);}Vector operator + (const Vector &v) const{return (Vector){x+v.x,y+v.y};}Vector operator - (const Vector &v) const{return (Vector){x-v.x,y-v.y};}Vector operator * (const int &k) const{return (Vector){x*k,y*k};}Vector operator / (const int &k) const{return (Vector){x/k,y/k};}
};
typedef Vector Point;
double dot(Vector v,Vector u)
{return v.x*u.x+v.y*u.y;
}
double cross(Vector v,Vector u)
{return v.x*u.y-v.y*u.x;
}
double length(Vector v)
{return sqrt(dot(v,v));
}
double dis(Point p,Point q)
{return length(p-q);
}
double convert(double a)
{while (dcmp(a)==-1) a+=2*pi;while (dcmp(a-2*pi)>=0) a-=2*pi;return a;
}
struct Circle
{Point o;double r;void rd(){scanf("%lf",&r);o.rd();}
}a[1010];
bool in(Circle c1,Circle c2)
{return dcmp(dis(c1.o,c2.o)-(c2.r-c1.r))<=0;
}
vector<pair<double,int> > ang;
vector<pair<double,int> >::iterator it;
void getintersection(Circle c1,Circle c2)
{double d=dis(c1.o,c2.o);if (dcmp(d-(c1.r+c2.r))>=0||dcmp(d-(c1.r-c2.r))<=0) return;double a1=atan2(c2.o.y-c1.o.y,c2.o.x-c1.o.x),a2=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));double s=convert(a1-a2),t=convert(a1+a2);if (dcmp(s-t)==1){ang.push_back(make_pair(0,1));ang.push_back(make_pair(t,-1));ang.push_back(make_pair(s,1));ang.push_back(make_pair(2*pi,-1));}else{ang.push_back(make_pair(s,1));ang.push_back(make_pair(t,-1));}
}
double count()
{double ret=0;int cnt=0;sort(ang.begin(),ang.end());if (ang.empty()) return 0;for (it=ang.begin();(it+1)!=ang.end();it++){cnt+=(*it).second;if (cnt) ret+=(*(it+1)).first-(*it).first;}return ret;
}
void check()
{for (it=ang.begin();it!=ang.end();it++)printf("%.3f %.3f\n",(*it).first,(*it).second);
}
int n;
int main()
{/*freopen("disc.in","r",stdin);freopen("disc.out","w",stdout);*/int ok;double ans=0;scanf("%d",&n);for (int i=1;i<=n;i++) a[i].rd();for (int i=1;i<=n;i++){ang.clear();ok=1;for (int j=i+1;j<=n&&ok;j++){if (in(a[i],a[j])) ok=0;else getintersection(a[i],a[j]);}if (ok) ans+=a[i].r*(2*pi-count());/*if (i==4) check();if (dcmp(ans)==-1){printf("%d\n",i);break;}*/}printf("%.3f\n",ans);
}