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


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

　　

看不懂系列》》》》

借助這道題補(bǔ)一下計(jì)算幾何中的部分知識(shí)

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

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

3.點(diǎn)積：

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

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

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

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

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

4.叉積：

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

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

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

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

（2：判斷折線拐向，可轉(zhuǎn)化為判斷第三點(diǎn)在前兩的形成直線的順逆時(shí)針?lè)较?#xff0c;然后判斷拐向。

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

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

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

5.凸包：graham掃描法

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

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

需要注意的是，如果一系列點(diǎn)按逆時(shí)針排列算出的是正面積，而如果是順時(shí)針的話算出的則是一個(gè)負(fù)面積。

?

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

總結(jié)

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

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