題目：https://www.lydsy.com/JudgeOnline/problem.php?id=2178
先看到這篇博客：https://www.cnblogs.com/heisenberg-/p/6740654.html
好像本應算弓形面積、三角形面積之類的，但不會...于是用辛普森積分硬做...
參考了這篇博客：https://blog.csdn.net/orpinex/article/details/7311363
然而如果寫成精度友好型的 asr ( *15, /15, eps/2 )，或T或RE的，不精度友好反而好了...
為什么一開始傳的范圍是所有圓邊界的 min, max 就會WA，傳 -inf, inf 就A了...
總之寫的時候還是盡量穩妥一點吧...
代碼如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef double db; int const xn=1005,inf=2005; db const eps=1e-8; int n; bool tmp[xn]; struct N{int x,y,r;}c[xn]; struct S{db l,r;}seg[xn]; int rd() {int ret=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return f?ret:-ret; } int dmp(db x) {if(fabs(x)<eps)return 0;else if(x>eps)return 1;else return -1; } db sqr(db x){return x*x;} bool cmp(S a,S b){return dmp(a.l-b.l)<0||(dmp(a.l-b.l)==0&&dmp(a.r-b.r)<0);} bool cmp2(N a,N b){return a.r<b.r;} db maxx(db x,db y){if(dmp(x-y)<0)return y; return x;} bool in(int a,int b){return sqr(c[a].x-c[b].x)+sqr(c[a].y-c[b].y)<=sqr(c[a].r-c[b].r);} void init() {sort(c+1,c+n+1,cmp2);for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++)if(in(i,j)){tmp[i]=1; break;}}int tot=0;for(int i=1;i<=n;i++)if(!tmp[i])c[++tot]=c[i];n=tot; } db f(db x) {int cnt=0;for(int i=1;i<=n;i++){if(dmp(fabs(c[i].x-x)-c[i].r)>0)continue;db dis=sqrt(sqr(c[i].r)-sqr(x-c[i].x));seg[++cnt].l=c[i].y-dis; seg[cnt].r=c[i].y+dis;}sort(seg+1,seg+cnt+1,cmp);db ret=0,r=-inf;for(int i=1;i<=cnt;i++){if(dmp(seg[i].l-r)>0)ret+=seg[i].r-seg[i].l,r=seg[i].r;else if(dmp(seg[i].r-r)>0)ret+=seg[i].r-r,r=seg[i].r;}return ret; } db simp(db l,db r){return (r-l)/6*(f(l)+4*f((l+r)/2)+f(r));} db asr(db l,db r,db eps,db lst) {db mid=(l+r)/2;db ls=simp(l,mid),rs=simp(mid,r);if(fabs(ls+rs-lst)<=15*eps)return ls+rs+(ls+rs-lst)/15;return asr(l,mid,eps/2,ls)+asr(mid,r,eps/2,rs); } db asr(db l,db r,db lst) {db mid=(l+r)/2;db ls=simp(l,mid),rs=simp(mid,r);if(fabs(ls+rs-lst)<=eps)return ls+rs;return asr(l,mid,ls)+asr(mid,r,rs); } int main() {n=rd(); int L=inf,R=-inf;for(int i=1;i<=n;i++)c[i].x=rd(),c[i].y=rd(),c[i].r=rd(),L=min(L,c[i].x-c[i].r),R=max(R,c[i].x+c[i].r);init();//printf("%.3f\n",asr(L,R,eps,simp(L,R)));//printf("%.3f\n",asr(L,R,simp(L,R)));printf("%.3f\n",asr(-inf,inf,simp(-inf,inf)));//printf("%.3f\n",asr(-inf,inf,eps,simp(-inf,inf)));return 0; }
?
然而這樣其實會錯HAHA，隨便來個數據竟然就錯了：
3
0 0 1
0 0 1
100 100 1
應該輸出 6.283，但上面的代碼以及許多題解輸出都是 3.142 ...
于是換了一種寫法，對每個連續段做積分，這樣避免了空白區域對積分結果的影響；
而且發現求一次 f(x) 很慢，所以之前求過的盡量重復利用；
然后就T了，調了兩小時...
TLE 的原因竟然是 sort 里面傳了 cmp() 函數？？！！！如果改成重載結構體小于號，就不T了呵呵-_-
所以還是要注意代碼習慣阿。
代碼如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef double db; int const xn=1005,inf=2005; db const eps=1e-13; int n,st,ed,xl[xn],xr[xn]; bool tmp[xn]; struct N{int x,y,r;bool operator < (const N &b) const{return r<b.r;} }c[xn]; struct S{db l,r;bool operator < (const S &b) const{return l<b.l;} }seg[xn]; int rd() {int ret=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return f?ret:-ret; } db sqr(db x){return x*x;} //bool cmp(S a,S b){return a.l<b.l;} //bool cmp2(N a,N b){return a.r<b.r;} bool cmp3(N a,N b){return a.x-a.r<b.x-b.r;} bool in(int a,int b){return sqr(c[a].x-c[b].x)+sqr(c[a].y-c[b].y)<=sqr(c[a].r-c[b].r);} void init() {sort(c+1,c+n+1);//cmp2for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++)if(in(i,j)){tmp[i]=1; break;}}int tot=0;for(int i=1;i<=n;i++)if(!tmp[i])c[++tot]=c[i];n=tot;sort(c+1,c+n+1,cmp3);// } db f(db x) {int cnt=0;for(int i=st;i<=ed;i++){if(xl[i]>=x||xr[i]<=x)continue;db dis=sqrt(c[i].r-sqr(x-c[i].x));//(sqr)seg[++cnt].l=c[i].y-dis; seg[cnt].r=c[i].y+dis;}sort(seg+1,seg+cnt+1);//cmpdb ret=0,r=-inf;for(int i=1,j;i<=cnt;i=j){r=seg[i].r;for(j=i+1;j<=cnt&&seg[j].l<=r;j++)if(r<seg[j].r)r=seg[j].r;ret+=r-seg[i].l; }return ret; } db simp(db len,db fl,db fr,db fm){return len/6*(fl+4*fm+fr);} db asr(db l,db r,db mid,db fl,db fr,db fm,db lst) {db lmid=(l+mid)/2,flm=f(lmid),rmid=(mid+r)/2,frm=f(rmid);db ls=simp(mid-l,fl,fm,flm),rs=simp(r-mid,fm,fr,frm);if(fabs(ls+rs-lst)<=eps)return ls+rs;return asr(l,mid,lmid,fl,fm,flm,ls)+asr(mid,r,rmid,fm,fr,frm,rs); } int main() {n=rd();for(int i=1;i<=n;i++)c[i].x=rd(),c[i].y=rd(),c[i].r=rd();init(); db ans=0;for(int i=1;i<=n;i++)xl[i]=c[i].x-c[i].r,xr[i]=c[i].x+c[i].r,c[i].r=c[i].r*c[i].r;for(int i=1,j;i<=n;i=j){int l=xl[i],r=xr[i];for(j=i+1;xl[j]<=r&&j<=n;j++)if(xr[j]>r)r=xr[j];st=i; ed=j-1; db mid=(l+r)/2;db fl=f(l),fm=f(mid),fr=f(r);ans+=asr(l,r,mid,fl,fr,fm,simp(r-l,fl,fr,fm));}printf("%.3f\n",ans);return 0; }
?
