題目鏈接

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16754

題目大意

求圓的面積并

思路

首先膜拜一發福大核武的神做法
http://hi.baidu.com/aekdycoin/item/b8ff6adc73c0e71dd78ed0d6
這種做法在applepi大爺的計算幾何講義中也有提到過，非常神奇優美，但是很不好寫，畢竟不是所有人都像核武大爺那樣神犇，沒有很強的可推廣性。

再來膜拜一發七爺的自適應Simpson積分題解
http://hi.baidu.com/sevenkplus/item/8cf47779e1e83b376cc37caa

自適應Simpson積分來求圓并的做法，就是用f(x)來表示一根穿過了橫坐標為x的掃描線，被圓形覆蓋的長度，那么f(x)的圖像是在一段一段的區間中是連續的，并且函數的曲線肯定是在x軸的上方。而且顯然最終的圓并面積就是f(x)的圖像與x軸圈起來的面積，我們可以用數值積分來求這個圖像的面積，數值積分分三種：矩形、梯形、Simpson，其中Simpson積分的做法就是把函數圖像用一根二次函數曲線來擬合，精度最高。
而自適應Simpson積分，簡單地說就是在當前區間直接擬合的精度足夠的情況下，就不會繼續遞歸到左右兩半區間再做Simpson積分，提高了算法的效率。

看起來這個玩意就是亂搞嘛是不是= =，似乎看上去很不靠譜，但是實際上非常好用，除非一些特殊的反例(http://wapapp.baidu.com/shuxk/item/bd1210284b5d2e869c63d1b7)，不光是圓的面積并，只要你會求出某種圖形蓋在掃描線上的區間，幾乎任何玩意的面積并都是可以求的，實為殺人越貨之利器23333。

那么我們就是要把所有圓分成一坨一坨圓，每一坨圓是連在一塊的，對于每一坨圓，它們的f(x)圖像肯定是連續的，就能用自適應Simpson積分把這一坨圓的面積求出來，累加答案即可。
當然還要注意怎么求一根掃描線被圓覆蓋的長度，這和之前我做的下落的圓盤那題差不多，也是個比較簡單的區間貪心問題，而找一坨一坨圓也是一樣的貪心，只不過是在x軸上做貪心而已，怎么做相信大家都會，渣渣我就不說了。

嘴巴上講講做法當然很簡單，但是我還是花了一個白天的時間才A掉這題，因此還要注意一些細節：
1、EPS開1e-6足矣，1e-7也可以，不過速度慢了4倍
2、此題很卡精度和細節，判<EPS神馬的必須取等號，比如說寫成<<script id="MathJax-Element-1121" type="math/tex"><</script>EPS就會WA，寫成<=<script id="MathJax-Element-1122" type="math/tex"><=</script>EPS就沒問題，不過在1e-7精度下沒問題，坑爹啊
3、找區間并的長度的貪心很簡單，但是還是要注意，不能掉以輕心（看我注釋中的感嘆號就是我WA的地方）
4、要做一個預處理，刪掉所有被其他大圓完全覆蓋的小圓，否則會WA，不要問我為什么，我也不知道，親測WA，扒了別人代碼才發現問題的。

代碼

//自適應Simpson積分 #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <cmath>#define MAXN 10000 #define EPS 1e-6using namespace std;int n;struct Point //點 {double x,y;Point(){}Point(double _x,double _y):x(_x),y(_y){}bool operator<(const Point &b)const { return x==b.x?y<b.y:x<b.x; } };struct Circle //圓 {Point o;double r;Circle(){}Circle(Point _o,double _r):o(_o),r(_r){} }circles[MAXN],tmp[MAXN];bool cmp2(Circle a,Circle b) {return a.r>b.r; }bool cmp(Circle a,Circle b) {if(fabs(a.o.x-a.r-b.o.x+b.r)<=EPS) return a.o.x+a.r<b.o.x+b.r;return a.o.x-a.r<b.o.x-b.r; }pair<double,double>intervals[MAXN]; int tot=0; int st,ed;bool check(Circle a,Circle b) //檢查b是否被套在a里面 {return (a.o.x-b.o.x)*(a.o.x-b.o.x)+(a.o.y-b.o.y)*(a.o.y-b.o.y)<=(a.r-b.r)*(a.r-b.r); }void prework() {sort(circles+1,circles+n+1,cmp2);int cnt=0;for(int i=1;i<=n;i++){bool flag=true;for(int j=1;j<=cnt;j++)if(check(tmp[j],circles[i])){flag=false;break;}if(flag) tmp[++cnt]=circles[i];}n=cnt;for(int i=1;i<=n;i++)circles[i]=tmp[i]; }void getCircleIntersec(Circle a,double x) //求x=x這條平行于y軸的直線穿過圓a的長度 {intervals[++tot]=make_pair(a.o.y-sqrt(a.r*a.r-(x-a.o.x)*(x-a.o.x)),a.o.y+sqrt(a.r*a.r-(x-a.o.x)*(x-a.o.x))); }double f(double x) //求掃描線x被圓覆蓋部分的長度 {tot=0;for(int i=st;i<=ed;i++)if(x<circles[i].o.x+circles[i].r&&x>circles[i].o.x-circles[i].r)getCircleIntersec(circles[i],x);sort(intervals+1,intervals+tot+1);double ans=0,start=-1e12,end=-1e12; //!!!!!!!!!!!for(int i=1;i<=tot;i++){if(intervals[i].first>=end){ans+=end-start;start=intervals[i].first;end=intervals[i].second;}else end=max(end,intervals[i].second);}ans+=end-start;return ans; }double calc(double len,double fL,double fM,double fR) //求長度為len的[L,R]區間，中點為M的Simpson近似面積 {return (fL+4*fM+fR)*len/6; }double Simpson(double L,double M,double R,double fL,double fM,double fR,double sqr) //Simpson積分求區間[L,R]的面積并,f(L)=L,f(R)=R,f(M)=M,把[L,R]當成整體來擬合得到的面積是sqr {double M1=(L+M)/2,M2=(M+R)/2;double fM1=f(M1),fM2=f(M2);double g1=calc(M-L,fL,fM1,fM),g2=calc(R-M,fM,fM2,fR);if(fabs(sqr-g1-g2)<=EPS) //把當前區間分成2半再擬合得到的答案差別很小，就不再遞歸下去了return g1+g2;return Simpson(L,M1,M,fL,fM1,fM,g1)+Simpson(M,M2,R,fM,fM2,fR,g2); }int main() {double ans=0;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&circles[i].o.x,&circles[i].o.y,&circles[i].r);prework();sort(circles+1,circles+n+1,cmp);for(int i=1,j;i<=n;i++){double L=circles[i].o.x-circles[i].r,R=circles[i].o.x+circles[i].r;for(j=i+1;j<=n;j++){if(circles[j].o.x-circles[j].r>R) break;else R=max(R,circles[j].o.x+circles[j].r); //!!!!!!!!!!!!!!}double M=(L+R)/2;st=i,ed=j-1;i=j-1;double fL=f(L),fM=f(M),fR=f(R);ans+=Simpson(L,M,R,fL,fM,fR,calc(R-L,fL,fM,fR));}printf("%.3lf\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的[SPOJ CIRU]The area of the union of circles(自适应Simpson积分求圆并面积)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。