暴力求圆的面积并

前言：

这个问题是集训时看到这道题后，再想要着手学习的。本篇中给出的做法复杂度并不能完全通过本题。

时限：7S,空间限制：512M

解法：

首先画图：

可以发现圆的面积并等于中间一些多边形（不一定是凸的）的面积+每个圆未被其它圆所覆盖的弓形的面积。所以就对于每个圆，求出其被覆盖的圆弧部分，这些部分形成了一些区间，然后先把区间合并起来，然后就可以叉积求出每个圆的被覆盖的多边形面积和未被覆盖的弓形面积。

#include 
using namespace std;
const double pi=acos(-1);
const int maxn=2005;
inline int read(){char c=getchar();int t=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}return t*f;
}
double rs,rb;
int ns,nb,t;
struct node{double x,y;node(double xx=0,double yy=0){x=xx,y=yy;}
}a[maxn];
node operator +(node a,node b){return node(a.x+b.x,a.y+b.y);}
node operator -(node a,node b){return node(a.x-b.x,a.y-b.y);}
double operator *(node a,node b){return a.x*b.x+a.y*b.y;}
node operator *(node a,double b){return node(a.x*b,a.y*b);}
node operator /(node a,double b){return node(a.x/b,a.y/b);}
double cross(node a,node b){return a.x*b.y-a.y*b.x;}
double dist(node a,node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
struct data{node ax,ay;double x,y;
}c[maxn];
double R[maxn];
int cho[maxn],alfa[maxn];
int n,b[maxn],m,l;
double ans1,ans2;
bool operator <(data a,data b){return (a.x<b.x)||((a.x==b.x)&&(a.y<b.y));
}
inline node rot(node p,double a){return node(cos(a)*p.x-sin(a)*p.y,sin(a)*p.x+cos(a)*p.y);
}
inline double deg(node p){double tmp=atan2(p.y,p.x);return tmp<0?tmp+2*pi:tmp;
}
inline void work(node o1,node o2,double r1,double r2){double s,p,h,alfa,tmp=dist(o1,o2);p=(r1+r2+tmp)/2;s=sqrt(p*(p-r1)*(p-r2)*(p-tmp));//海伦公式求面积 h=s*2/tmp;alfa=asin(h/r1);//h：高,alfa：夹角 if(r1*r1+tmp*tmp<r2*r2)alfa=pi-alfa;//如果是钝角 m++;c[m].ax=rot(o2-o1,pi*2-alfa)/tmp*r1+o1;//求交点 c[m].ay=rot(o2-o1,alfa)/tmp*r1+o1;c[m].x=deg(c[m].ax-o1);//求出两个交点的极角 c[m].y=deg(c[m].ay-o1);if(c[m].x>c[m].y){//如果两个交点形成的弧跨过了2pi,就需要把弧拆成两段。 m++;c[m].y=c[m-1].y;c[m].ay=c[m-1].ay;c[m-1].y=pi*2;c[m].x=0;c[m-1].ay=c[m].ax=o1+node(r1,0);}
}
int main() {//freopen("c.in","r",stdin);//freopen("c.out","w",stdout);scanf("%lf%lf",&rs,&rb);t=read();while(t--){ns=read();nb=read();n=ns+nb;for(int i=1;i<=ns;i++){a[i].x=read();a[i].y=read();R[i]=rs;}for(int i=ns+1;i<=ns+nb;i++){a[i].x=read(),a[i].y=read();R[i]=rb;}if(ns+nb==1){if(nb)printf("%.3lf\n",pi*rb*rb);else printf("%.3lf\n",pi*rs*rs);continue;}memset(b,0,sizeof(b));for(int i=1;i<=n;i++){if(!b[i]){for(int j=1;j<=n;j++){if((!b[j])&&(i!=j)&&(dist(a[i],a[j])<=R[j]-R[i])){//	printf("%d %d %lf %lf %lf %lf\n",i,j,a[i].x,a[i].y,a[j].x,a[j].y);b[i]=1;break;}}}}ans1=ans2=0;for(int i=1;i<=n;i++){if(!b[i]){m=0;for(int j=1;j<=n;j++){if((!b[j])&&(i!=j)&&dist(a[i],a[j])<=R[j]+R[i]){work(a[i],a[j],R[i],R[j]);}}if(m==0){ans2+=pi*R[i]*R[i];continue;}sort(c+1,c+1+m);c[0].y=0;c[m+1].x=pi*2;c[0].ay=c[m+1].ax=a[i]+node(R[i],0);double tmp=0;int k;for(int j=0;j<=m;j=k+1){for(k=l=j;k<m&&c[k+1].x<=c[l].y;k++){if(c[k+1].y>c[l].y) l=k+1;}ans1+=cross(c[l].ay,c[k+1].ax);tmp=c[k+1].x-c[l].y;ans2+=R[i]*R[i]*(tmp-sin(tmp))/2;}}}printf("%.5lf\n",fabs(ans1)/2+ans2);}return 0;
}

其实思路并不是很难，但是实现起来比较麻烦。时间复杂度 O ( t × n 2 l o g n ) O(t\times n^2logn) O(t×)