問題描述 作為水污染管理部門的一名雇員，你需要監(jiān)控那些被有意無意倒入河流、湖泊和海洋的污染物。你的其中一項工作就是估計污染物對不同的水生態(tài)系統(tǒng)（珊瑚礁、產(chǎn)卵地等等）造成的影響。


　　你計算所使用的模型已經(jīng)在圖1中被說明。海岸線（圖1中的水平直線）為x軸，污染源位于原點(0, 0)。污染的蔓延呈半圓形，多邊形代表了被波及的生態(tài)系統(tǒng)。你需要計算出生態(tài)系統(tǒng)被污染的面積，也就是圖中深藍色部分。 輸入格式 輸入文件包含僅包含一組測試數(shù)據(jù)。
　　每組測試數(shù)據(jù)第一行為兩個整數(shù)n (3 <= n <= 100), r (1 <= r <= 1000)，n表示了多邊形的頂點個數(shù)，r表示了污染區(qū)域的半徑；
　　接下來n行，每行包含兩個整數(shù)xi (-1500 <= xi <= 1500), yi (0 <= yi <=1500)，表示每個頂點的坐標(biāo)，以逆時針順序給出；
　　數(shù)據(jù)保證多邊形不自交或觸及自身，沒有頂點會位于圓弧上。 輸出格式 輸出多邊形被圓心位于原點、半徑為r的半圓覆蓋的面積。
　　答案的絕對誤差不得超過10^-3。 樣例輸入 6 10
-8 2
8 2
8 14
0 14
0 6
-8 14 樣例輸出 101.576437872 數(shù)據(jù)規(guī)模和約定 存在約30%的數(shù)據(jù)，n = 3，r <= 20；
　　存在另外約30%的數(shù)據(jù)，n <= 10，r <= 100，坐標(biāo)范圍不超過100；
　　存在另外約10%的數(shù)據(jù)，n <= 100，r <= 150，坐標(biāo)范圍不超過250；
　　存在另外約30%的數(shù)據(jù)，n <= 100，r <= 1000，數(shù)據(jù)存在梯度；
　　對于100%的數(shù)據(jù)，滿足題目所示數(shù)據(jù)范圍。

?

題解

#include<iostream> #include<math.h> #include<cstdio> #include<algorithm> #include<string> #include<queue> #include<cctype> #include<cstring> #include<map> using namespace std; const int N=1e2+5; const int M=N/2;int n,r; int X[N],Y[N];struct P{double x,y;double getlength(){return sqrt(x*x+y*y);}bool incircle(){return x*x+y*y<=r*r;}double cross(P &b){return x*b.y-y*b.x;} }; double getArea(P &a,P &b){double degree=a.cross(b)/a.getlength()/b.getlength();if(degree<-1)degree=-1;if(degree>1)degree=1;degree=asin(degree);return r*r*degree/2; } double cal(P &a,P &b){bool in1 = a.incircle();bool in2 = b.incircle();if(in1&&in2){return a.cross(b)/2;}else if(in1!=in2){P l=a;P r=b;P mid;for(int i=0;i<40;i++){mid=P{(l.x+r.x)/2,(l.y+r.y)/2};if(mid.incircle()==in1){l=mid;}else{r=mid;}}if(in1){return a.cross(mid)/2+getArea(mid,b);}else{return getArea(a,mid)+mid.cross(b)/2;}}else{P l=a;P r=b;P mid;P midr;for(int i=0;i<40;i++){mid=P{(l.x+r.x)/2,(l.y+r.y)/2};midr=P{(l.x+r.x)/2+(r.x-l.x)*0.0001,(l.y+r.y)/2+(r.y-l.y)*0.0001};if(mid.getlength()<midr.getlength()){r=mid;}else{l=mid;}}if(mid.incircle()){return cal(a,mid)+cal(mid,b);}else{return getArea(a,b);}} }int main() {cin>>n>>r;for(int i=0;i<n;i++){cin>>X[i]>>Y[i];}X[n]=X[0];Y[n]=Y[0];double ans=0;for(int i=0;i<n;i++){P a=P{X[i],Y[i]};P b=P{X[i+1],Y[i+1]};ans+=cal(a,b);}printf("%lf\n",ans);return 0; }

　　

看不懂系列》》》》

借助這道題補一下計算幾何中的部分知識

1.容斥定理：要計算幾個集合并集的大小，我們要先將所有單個集合的大小計算出來，然后減去所有兩個集合相交的部分，再加回所有三個集合相交的部分，再減去所有四個集合相交的部分，依此類推，一直計算到所有集合相交的部分。

2.四色定理：四色問題的內(nèi)容是“任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。”也就是說在不引起混淆的情況下一張地圖只需四種顏色來標(biāo)記就行。

3.點積：

點：A（x1，y1），B（x2，y2） 向量：向量AB=（ x2 - x1 , y2 - y1 ）= ( x , y );

向量的模 |AB| = sqrt ( x*x+y*y );

向量的點積： 結(jié)果為 x1*x2 + y1*y2。 點積的結(jié)果是一個數(shù)值。

點積的集合意義：我們以向量 a 向向量 b 做垂線，則 | a | * cos（a,b）為 a 在向量 b 上的投影，即點積是一個向量在另一個向量上的投影乘以另一個向量。且滿足交換律

應(yīng)用：可以根據(jù)集合意義求兩向量的夾角， cos（a,b） =（ 向量a * 向量b ） / （| a | * | b |） = x1*x2 + y1*y2 / （| a | * | b |）

4.叉積：

向量的叉積： 結(jié)果為 x1*y2-x2*y1 叉積的結(jié)果也是一個向量，是垂直于向量a，b所形成的平面，如果看成三維坐標(biāo)的話是在 z 軸上，上面結(jié)果是它的模。

方向判定：右手定則，（右手半握，大拇指垂直向上，四指右向量a握向b，大拇指的方向就是叉積的方向）

叉積的集合意義： 1：其結(jié)果是a和b為相鄰邊形成平行四邊形的面積。 2：結(jié)果有正有負，有sin（a，b）可知和其夾角有關(guān)，夾角大于180°為負值。 3：叉積不滿足交換律

應(yīng)用： （1：通過結(jié)果的正負判斷兩矢量之間的順逆時針關(guān)系 若 a x b > 0表示a在b的順時針方向上 若 a x b < 0表示a在b的逆時針方向上 若 a x b == 0表示a在b共線，但不確定方向是否相同

（2：判斷折線拐向，可轉(zhuǎn)化為判斷第三點在前兩的形成直線的順逆時針方向，然后判斷拐向。

（3：判斷一個點在一條直線的那一側(cè)，同樣上面的方法。

（4：判斷點是否在線段上，可利用叉乘首先判斷是否共線，然后在判斷是否在其上。

（5：判斷兩條直線是否想交（跨立實驗） 根據(jù)判斷點在直線那一側(cè)我們可以判斷一個線段的上的兩點分別在另一個線段的兩側(cè)，當(dāng)然這是不夠的，因為我們畫圖發(fā)現(xiàn)這樣只能夠讓直線想交，而不是線段，所以我們還要對另一條線段也進行相同的判斷就ok。

5.凸包：graham掃描法

6.皮克公式：（計算多邊形的面積）

S = 1/2×( ( X1*Y2-X2*Y1 ) + … + ( Xk*Yk+1-Xk+1*Yk ) + ... + ( Xn*Y1-X1*Yn ) )

需要注意的是，如果一系列點按逆時針排列算出的是正面積，而如果是順時針的話算出的則是一個負面積。

?

轉(zhuǎn)載于:https://www.cnblogs.com/ruruozhenhao/p/8419734.html

總結(jié)

以上是生活随笔為你收集整理的算法训练 Pollution Solution（计算几何）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。