首页 > 代码库 > bzoj 2178 自适应Simpson积分
bzoj 2178 自适应Simpson积分
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 using namespace std; 8 int n; 9 const double eps = 1e-13; 10 struct node 11 { 12 double x,y,r; 13 }b[1006],a[1006];int cnt; 14 bool cmp1(node aa,node bb) 15 { 16 return aa.r<bb.r; 17 } 18 bool v[1005]; 19 double dis(int x,int y) 20 { 21 return sqrt((b[x].x-b[y].x)*(b[x].x-b[y].x)+(b[x].y-b[y].y)*(b[x].y-b[y].y)); 22 } 23 double lmin,rmax; 24 pair<double,double>q[1005]; 25 double mx(double x,double y) 26 { 27 return x<y?y:x; 28 } 29 double f(double x) 30 { 31 int top=0;double len=0; 32 for(int i=1;i<=cnt;i++) 33 { 34 double xx=fabs(a[i].x-x); 35 if(fabs(xx)<=a[i].r) 36 { 37 double ww=sqrt(a[i].r*a[i].r-xx*xx); 38 q[++top].first=a[i].y-ww; 39 q[top].second=a[i].y+ww; 40 } 41 } 42 sort(q+1,q+top+1);len+=q[1].second-q[1].first; 43 double rs=q[1].second; 44 for(int i=2;i<=top;i++)if(q[i].second>rs)len+=q[i].second-mx(q[i].first,rs),rs=q[i].second; 45 return len; 46 } 47 double asr(double l,double mid,double r,double A,double B,double C) 48 { 49 double s=((r-l)/6)*(A+4*B+C),lf=f((l+mid)/2),rf=f((mid+r)/2); 50 double ls=((mid-l)/6)*(A+B+4*lf),rs=((r-mid)/6)*(B+C+4*rf); 51 if(fabs(s-ls-rs)<=eps)return s; 52 return asr(l,(l+mid)/2,mid,A,lf,B)+asr(mid,(r+mid)/2,r,B,rf,C); 53 } 54 int main() 55 { 56 scanf("%d",&n); 57 for(int i=1;i<=n;i++) 58 { 59 scanf("%lf%lf%lf",&b[i].x,&b[i].y,&b[i].r); 60 lmin=min(lmin,b[i].x-b[i].r);rmax=max(rmax,b[i].x+b[i].r); 61 } 62 sort(b+1,b+n+1,cmp1); 63 for(int i=1;i<=n;i++) 64 { 65 for(int j=1;j<i;j++) 66 { 67 if(dis(i,j)<=b[i].r-b[j].r)v[j]=1; 68 } 69 } 70 for(int i=1;i<=n;i++)if(!v[i])a[++cnt]=b[i]; 71 printf("%.3f\n",asr(lmin,(lmin+rmax)/2,rmax,0,f((lmin+rmax)/2),0)); 72 return 0; 73 }
bzoj 2178 自适应Simpson积分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。