首页 > 其他 > 详细

BZOJ2178 圆的面积并

时间:2019-03-16 10:21:06      阅读:30      评论:0      收藏:0      [点我收藏+]

标签:2.0   spa   数值   std   per   lin   etc   sin   ==   

BZOJ2178 圆的面积并

题面:权限题,大意就是给你\(n\)个圆,求它们的面积并。

解析

计算奇奇怪怪的面积可以使用自适应辛普森法,对每一个\(x_0\),与之对应的函数值是直线\(x=x_0\)与所有圆的相交线段的并,积分即可得到面积。

代码


#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 圆的面积并

标签:2.0   spa   数值   std   per   lin   etc   sin   ==   

原文:https://www.cnblogs.com/pkh68/p/10540542.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号