直接辛普森积分，我是照着nixy的模版写的。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n;
const double eps=1e-9;
struct Circle{
double x,y,r;
friend bool operator<(Circle a,Circle b){
return a.r<b.r;
}
}cir[1005];
struct Line{
double l,r;
Line(double kl=0,double kr=0){l=kl;r=kr;}
}line[1005];
double Dist(Circle a,Circle b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(Line a,Line b){
return a.l<b.l;
}
double F(double x){
int lx=0;
for(int i=1;i<=n;i++){
double ex=(x-cir[i].x)*(x-cir[i].x);
if(ex>cir[i].r)continue;
ex=sqrt(cir[i].r-ex);
line[++lx]=Line(cir[i].y-ex,cir[i].y+ex);
}
if(lx==0)return 0;
sort(line+1,line+lx+1,cmp);
double L=line[1].l,R=line[1].r,res=0;
for(int i=2;i<=lx;i++){
if(line[i].l<=R){R=max(line[i].r,R);}
else {res+=R-L;L=line[i].l;R=line[i].r;}
}
return res+R-L;
}
double Simpson(double l,double r,double Fl,double Fmid,double Fr){
return (Fl+Fr+4*Fmid)*(r-l)/6;
}
double Self_Adjust(double l,double r,double Fl,double Fmid,double Fr){
double mid=l/2+r/2;
double F1=F(l/2+mid/2),F2=F(mid/2+r/2);
if(r-l<2){
double S1=Simpson(l,mid,Fl,F1,Fmid),S2=Simpson(mid,r,Fmid,F2,Fr),Se=Simpson(l,r,Fl,Fmid,Fr);
if(fabs(Se-S1-S2)<eps)return S1+S2;
else return Self_Adjust(l,mid,Fl,F1,Fmid)+Self_Adjust(mid,r,Fmid,F2,Fr);
}
else return Self_Adjust(l,mid,Fl,F1,Fmid)+Self_Adjust(mid,r,Fmid,F2,Fr);
}
int main(){
freopen("2178.in","r",stdin);
freopen("2178.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf %lf %lf",&cir[i].x,&cir[i].y,&cir[i].r);
cir[i].r*=cir[i].r;
}
printf("%.3lf\n",Self_Adjust(-2000,2000,F(-2000),F(0),F(2000)));
return 0;
}
评论 (0)
