首页 > 代码库 > BZOJ 2178 Simpson积分

BZOJ 2178 Simpson积分

思路:

我发现能用Simpson积分水的题  好像都是裸题诶233333

//By SiriusRen#include <bits/stdc++.h>using namespace std;#define pr pair<double,double>const int N=1050;int n,ban[N];double inf=1e100,l=inf,r=-inf;pr p[N];struct Point{int x,y;};double dis(Point a,Point b){    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}struct Circle{    Point p;int r;    pr f(double x){        if(r<=abs(p.x-x))return pr(0,0);        double t=sqrt(r*r-(p.x-x)*(p.x-x));        return pr(1.0*p.y-t,1.0*p.y+t);    }}c[N];double Cut(double x){    double ret=0,last=-inf;int cnt=0;    for(int i=1;i<=n;i++){        p[++cnt]=c[i].f(x);        if(p[cnt]==pr(0,0))cnt--;    }    sort(p+1,p+1+cnt);    for(int i=1;i<=cnt;i++){        if(p[i].first>last)ret+=p[i].second-p[i].first,last=p[i].second;        else if(p[i].second>last)ret+=p[i].second-last,last=p[i].second;    }return ret;}double Simpson(double l,double r,double mid,double Cl,double Cr,double Cm){    double tCl=Cut((l+mid)/2),tCr=Cut((mid+r)/2);    double ans=(r-l)*(Cl+Cr+4*Cm)/6,lans=(mid-l)*(Cl+Cm+4*tCl)/6,rans=(r-mid)*(Cr+Cm+4*tCr)/6;    if(abs(lans+rans-ans)<1e-13)return ans;    else return Simpson(l,mid,(l+mid)/2,Cl,Cm,tCl)+Simpson(mid,r,(mid+r)/2,Cm,Cr,tCr); }int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d%d%d",&c[i].p.x,&c[i].p.y,&c[i].r);        l=min(l,(double)c[i].p.x-c[i].r);        r=max(r,(double)c[i].p.x+c[i].r);    }    for(int i=1;i<=n;i++){        if(ban[i])continue;        for(int j=i+1;j<=n;j++){            if(ban[j])continue;            if(dis(c[i].p,c[j].p)<=c[i].r-c[j].r)ban[j]=1;        }    }    for(int i=1;i<=n;i++)if(ban[i])swap(ban[i],ban[n]),swap(c[i--],c[n--]);    printf("%.3lf\n",Simpson(l,r,(l+r)/2,0,0,Cut((l+r)/2)));}

 

BZOJ 2178 Simpson积分