問題描述
作為水污染管理部門的一名雇員，你需要監控那些被有意無意倒入河流、湖泊和海洋的污染物。你的其中一項工作就是估計污染物對不同的水生态系統（珊瑚礁、産卵地等等）造成的影響。
你計算所使用的模型已經在圖1中被說明。海岸線（圖1中的水準直線）為x軸，污染源位于原點(0, 0)。污染的蔓延呈半圓形，多邊形代表了被波及的生态系統。你需要計算出生态系統被污染的面積，也就是圖中深藍色部分。
輸入格式
輸入檔案包含僅包含一組測試資料。
每組測試資料第一行為兩個整數n (3 <= n <= 100), r (1 <= r <= 1000)，n表示了多邊形的頂點個數，r表示了污染區域的半徑；
接下來n行，每行包含兩個整數xi (-1500 <= xi <= 1500), yi (0 <= yi <=1500)，表示每個頂點的坐标，以逆時針順序給出；
資料保證多邊形不自交或觸及自身，沒有頂點會位于圓弧上。
輸出格式
輸出多邊形被圓心位于原點、半徑為r的半圓覆寫的面積。
答案的絕對誤差不得超過10^-3。
樣例輸入
6 10
-8 2
8 2
8 14
0 14
0 6
-8 14
樣例輸出
101.576437872
資料規模和約定
存在約30%的資料，n = 3，r <= 20；
存在另外約30%的資料，n <= 10，r <= 100，坐标範圍不超過100；
存在另外約10%的資料，n <= 100，r <= 150，坐标範圍不超過250；
存在另外約30%的資料，n <= 100，r <= 1000，資料存在梯度；
對于100%的資料，滿足題目所示資料範圍。
題解
#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.四色定理：四色問題的内容是“任何一張地圖隻用四種顔色就能使具有共同邊界的國家着上不同的顔色。”也就是說在不引起混淆的情況下一張地圖隻需四種顔色來标記就行。
3.點積：
點：A（x1，y1），B（x2，y2） 向量：向量AB=（ x2 - x1 , y2 - y1 ）= ( x , y );
向量的模 |AB| = sqrt ( x*x+y*y );
向量的點積： 結果為 x1*x2 + y1*y2。 點積的結果是一個數值。
點積的集合意義：我們以向量 a 向向量 b 做垂線，則 | a | * cos（a,b）為 a 在向量 b 上的投影，即點積是一個向量在另一個向量上的投影乘以另一個向量。且滿足交換律
應用：可以根據集合意義求兩向量的夾角， cos（a,b） =（ 向量a * 向量b ） / （| a | * | b |） = x1*x2 + y1*y2 / （| a | * | b |）
4.叉積：
向量的叉積： 結果為 x1*y2-x2*y1 叉積的結果也是一個向量，是垂直于向量a，b所形成的平面，如果看成三維坐标的話是在 z 軸上，上面結果是它的模。
方向判定：右手定則，（右手半握，大拇指垂直向上，四指右向量a握向b，大拇指的方向就是叉積的方向）
叉積的集合意義： 1：其結果是a和b為相鄰邊形成平行四邊形的面積。 2：結果有正有負，有sin（a，b）可知和其夾角有關，夾角大于180°為負值。 3：叉積不滿足交換律
應用： （1：通過結果的正負判斷兩矢量之間的順逆時針關系 若 a x b > 0表示a在b的順時針方向上 若 a x b < 0表示a在b的逆時針方向上 若 a x b == 0表示a在b共線，但不确定方向是否相同
（2：判斷折線拐向，可轉化為判斷第三點在前兩的形成直線的順逆時針方向，然後判斷拐向。
（3：判斷一個點在一條直線的那一側，同樣上面的方法。
（4：判斷點是否線上段上，可利用叉乘首先判斷是否共線，然後在判斷是否在其上。
（5：判斷兩條直線是否想交（跨立實驗） 根據判斷點在直線那一側我們可以判斷一個線段的上的兩點分别在另一個線段的兩側，當然這是不夠的，因為我們畫圖發現這樣隻能夠讓直線想交，而不是線段，是以我們還要對另一條線段也進行相同的判斷就ok。
5.凸包：graham掃描法
6.皮克公式：（計算多邊形的面積）
永遠渴望，大智若愚（stay hungry, stay foolish）