bzoj 2178 圆的面积并——辛普森积分

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2178

把包含的圆去掉。横坐标不相交的一段一段圆分开算。算辛普森的时候预处理 f( ) ，比如把自己的 f( l ) 和 f( r ) 从上一层传进来之类的，能少算很多次。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define db double

using namespace std;

const int N=; const db eps=1e-;

db Fabs(db x){return x<?-x:x;}

db Sqr(db x){return x*x;}

int nMx(int a,int b){return a>b?a:b;}

db dMx(db a,db b){return a>b?a:b;}

int n,xl[N],xr[N],st,ed; db ans;

struct Cir{

  int r,x,y;

  bool operator< (const Cir &b)const

  {return r>b.r;}

}t[N];

struct Node{

  db l,r;

  Node(db a=,db b=):l(a),r(b) {}

  bool operator< (const Node &b)const

  {return l<b.l;}

}a[N];

bool cmp(Cir u,Cir v){return u.x-u.r<v.x-v.r;}

db f(db p)

{

  int cnt=; db ret=;

  for(int i=st;i<=ed;i++)

    if(xr[i]>p&&xl[i]<p)

      {

    db k=sqrt(t[i].r-Sqr(p-t[i].x));

    a[++cnt]=Node(t[i].y-k,t[i].y+k);

      }

  sort(a+,a+cnt+);

  for(int i=,j=;i<=cnt;i=j)

    {

      db L=a[i].l,R=a[i].r;

      for(j=i+;j<=cnt&&a[j].l<=R;j++)R=dMx(R,a[j].r);

      ret+=R-L;

    }

  return ret;

}

db cal(db fl,db fm,db fr,db d){return (fl+*fm+fr)*d/;}

db simp(db l,db mid,db r,db fl,db fm,db fr,db ret)

{

  db m1=(l+mid)*0.5,m2=(mid+r)*0.5,fm1=f(m1),fm2=f(m2);

  db vl=cal(fl,fm1,fm,mid-l),vr=cal(fm,fm2,fr,r-mid);

  if(Fabs(vl+vr-ret)<=eps)return vl+vr;

  return simp(l,m1,mid,fl,fm1,fm,vl)+simp(mid,m2,r,fm,fm2,fr,vr);

}

int main()

{

  scanf("%d",&n);

  for(int i=;i<=n;i++)

    scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].r);

  sort(t+,t+n+);

  for(int i=;i<=n;i++)

    for(int j=;j<i;j++)

      {

    db d=sqrt(Sqr(t[i].y-t[j].y)+Sqr(t[i].x-t[j].x));

    if(d+t[i].r<=t[j].r)

      {t[i--]=t[n--];break;}

      }

  sort(t+,t+n+,cmp);

  for(int i=;i<=n;i++)

    xl[i]=t[i].x-t[i].r,xr[i]=t[i].x+t[i].r,t[i].r*=t[i].r;

  int L,R;db fl,fr,mid,fm;

  for(int i=,j;i<=n;i=j)//j not j-1

    {

      L=xl[i];R=xr[i];

      for(j=i+;j<=n&&xl[j]<=R;j++)R=nMx(R,xr[j]);

      st=i;ed=j-;

      fl=f(L);fr=f(R);mid=(db)(L+R)*0.5;fm=f(mid);

      ans+=simp(L,mid,R,fl,fm,fr,cal(fl,fm,fr,R-L));

    }

  printf("%.3f\n",ans);

  return ;

}