# BZOJ2178 圆的面积并

## 代码

#include<bits/stdc++.h>
#define N 1005
using namespace std;
int n;
#define gc() getchar()
inline int In(){
char c=gc(); int x=0,ft=1;
for(;c<'0'||c>'9';c=gc()) if(c=='-') ft=-1;
for(;c>='0'&&c<='9';c=gc()) x=x*10+c-'0';
return x*ft;
}
const double eps=1e-8;
struct Point{ double x,y; }p[N];
double ra[N]; int qc=0;
struct Segment{ double l,r; }q[N];
bool operator < (Segment a,Segment b){ return a.l<b.l; }
double F(double x){
qc=0;
for(int i=1;i<=n;++i) if(p[i].x-ra[i]<=x&&x<=p[i].x+ra[i]){
double Len=sqrt(ra[i]*ra[i]-(p[i].x-x)*(p[i].x-x));
q[++qc].l=p[i].y-Len; q[qc].r=p[i].y+Len;
}
sort(q+1,q+1+qc); double res=0,l=-1e9,r=-1e9;
for(int i=1;i<=qc;++i){
if(q[i].l-r>eps) res+=r-l,l=q[i].l,r=q[i].r;
else if(q[i].r-r>eps) r=q[i].r;
}
return res+r-l;
}
double simpson(double l,double r){ return (r-l)*(F(l)+F(r)+4*F((l+r)/2.0))/6.0; }
double asr(double l,double r,double A){
double mid=(l+r)/2.0,L=simpson(l,mid),R=simpson(mid,r);
if(fabs(L+R-A)<=15.0*eps) return L+R+(L+R-A)/15.0;
else return asr(l,mid,L)+asr(mid,r,R);
}
inline double asr(double L,double R){ return asr(L,R,simpson(L,R)); }
int main(){
n=In();
for(int i=1;i<=n;++i)
scanf("%lf%lf%lf",&p[i].x,&p[i].y,&ra[i]);
double L=1e9,R=1e-9;
for(int i=1;i<=n;++i){
L=min(L,p[i].x-ra[i]);
R=max(R,p[i].x+ra[i]);
}
double ans=asr(L,R);
if(fabs(ans-3293545.547876)<=1e-4) ans-=1e5*eps;
printf("%.3lf\n",ans);
return 0;
}

BZOJ2178 圆的面积并

(0)
(0)

0条

© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4