---
tags: Training
type: slide
---
<style>
.reveal .slides {
text-align: left;
font-size:30px
}
</style>
# Geometry
## 計算幾何
Introduction to Competitive Programming
2022/06/01
----
- 浮點數誤差
- 向量與內外積
- 面積
- 各種計幾問題
- 凸包
- 旋轉卡尺
- 最遠點對
- 掃描線
- 矩形覆蓋面積
---
## 浮點數誤差
可以嘗試跑以下程式碼
```cpp=
double x = 0.0;
while(x != 1.0){
x += 0.1;
}
```
理論上在迴圈裡跑加 10 次就會結束了
但實際上執行會因為精確度誤差造成程式會停不下來
為了解決浮點數誤差的問題，通常會設一個很小的數字例如$10^{-9}$
在比較大小關係時，如果在誤差範圍內則視為相等
----
改成當前的值與目標若差值小於 EPS 則視為相同
```cpp=
#define EPS 1e-9
double x=0.0;
while(abs(x-1.0) > EPS){
x += 0.1;
}
// 控制輸出到小數點後 10 位
cout << fixed << setprecision(10) << x << endl;
```
而 EPS 大小則視不同題目而定
不同題目都有不同的精度限制
----
由於浮點數誤差是個很麻煩的問題
因此在寫計算幾何時，如果能避免使用浮點數則會盡量使用整數型態
像是判斷距離，當前點到點 u, v 哪個比較近
距離公式 $\sqrt{x^2+y^2}$ 會開根號
但實際上只需求出 $x^2+y^2$ 即可判斷兩者距離大小
只需使用 long long 型態即可
---
### 歐基里德距離
$d(p_1, p_2) = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2)}$
### 曼哈頓距離
$d(p_1, p_2) = |x_1-x_2|+|y_1-y_2|$
----
## 向量
$\vec{v} = (a, b)$，代表往 +x 軸走單位 $a$，往 +y 軸走單位 $b$
長度 $|\vec{v}|$ 為 $\sqrt{a^2+b^2}$
### 向量四則運算
假設有兩向量 $v_{1} = (x_1, y_1), v_{2} = (x_2, y_2)$
- $v_1 + v_2 = (x_1 + x_2, y_1 + y_2)$
- $v_1 - v_2 = (x_1 - x_2, y_1 - y_2)$
- $v_1 × k = (x_1 × k, y_1 × k)$ (向量伸長成 $k$ 倍)
- $v_1 ÷ k = (x_1 ÷ k, y_1 ÷ k)$ (向量縮短成 $k$ 倍)
----
### 內積
$\vec{v_{1}} =(x_1, y_1), \vec{v_{2}}=(x_2, y_2)$
$\vec{v_{1}} \cdot \vec{v_{2}} = x_1x_2 + y_1y_2 = |\vec{v_1}||\vec{v_2}| cos \theta$ $(\theta$ 為兩向量夾角)
兩向量同向，則內積為正
兩向量反向，則內積為負
兩向量垂直，則內積為 0
----
### 外積
$\vec{v_{1}} =(x_1, y_1), \vec{v_{2}}=(x_2, y_2)$
$\vec{v_{1}} \times \vec{v_{2}} = x_1y_2 -x_2y_1=|\vec{v_1}||\vec{v_2}| sin \theta$ $(\theta$ 為兩向量夾角)
$\vec{v_{1}} \times \vec{v_{2}} = - \vec{v_{2}} \times \vec{v_{1}}$ 具有負交換律
如果 $\vec{v_{1}}$ 到 $\vec{v_{2}}$ 為逆時鐘方向，則外積為正
如果 $\vec{v_{1}}$ 到 $\vec{v_{2}}$ 為順時鐘方向，則外積為負
兩向量平行則外積為 0
同時外積取絕對值(| $\vec{v_{1}} \times \vec{v_{2}}$ |)等同於兩向量夾起來的平行四邊形面積
----
### 儲存方法
#### 點 (儲存座標 x, y 表示)
```cpp
struct Pt{
ld x, y;
};
```
#### 線段 (儲存線段兩端點儲存)
```cpp
struct Line{
Pt st, ed;
};
```
#### 圓 (儲存圓心與半徑)
```cpp=
struct Circle{
Pt o; // 圓心
ld r; // 半徑
};
```
#### 多邊形 ( 用 vector 儲存所有點)
```cpp=
struct poly{
int n; // n 邊形
vector<Pt> pts;
};
```
----
## default code
```cpp=
#define ld long double
struct Pt {
ld x, y;
Pt(ld _x=0, ld _y=0):x(_x), y(_y) {}
Pt operator+(const Pt &a){
return Pt(x+a.x, y+a.y);
}
Pt operator-(const Pt &a){
return Pt(x-a.x, y-a.y);
}
Pt operator*(const ld &a){
return Pt(x*a, y*a);
}
Pt operator/(const ld &a){
return Pt(x/a, y/a);
}
ld operator*(const Pt &a){ //程式碼中內積通常用*表示
return x*a.x + y*a.y;
}
ld operator^(const Pt &a){ //程式碼中外積通常用^表示
return x*a.y - y*a.x;
}
bool operator<(const Pt &a) const {
return x < a.x || (x == a.x && y < a.y);
}
};
```
---
### 三角形面積
- 海龍公式
$s = \frac{a+b+c}{2}$ (a,b,c 為三角形三邊長)
$\triangle abc = \sqrt{s(s-a)(s-b)(s-c)}$
- 外積求法
|$\vec{v_1} \times \vec{v_2}$| 為所夾的平行四邊形面積
而平行四邊形的一半為三角形面積
因此 $\frac{|\vec{v_1} \times \vec{v_2}|}{2}$ 為三角形面積
----
### 多邊形面積
一個 $n$ 個點的多邊形($P_1, P_2,... P_n$)
可以拆成很多三角形，再分別套用外積公式
$\frac{1}{2}|\sum\limits_{i=1}^{n} \overrightarrow {OP_{i}} \times \overrightarrow {OP_{i+1}}|$
複雜度 $O(N)$
----
使用外積公式求面積會發現
$\frac{1}{2}|\sum\limits_{i=1}^{n} \overrightarrow {OP_{i}} \times \overrightarrow {OP_{i+1}}|$
如果所有點都為整數點，則除了最後乘 $\frac{1}{2}$ 使得面積有可能為小數，否則在用外積公式時都為整數運算
因此整數點的面積不是整數就是 .5 結尾
過程中可以完全不用用到小數可以避免浮點數誤差
---
### 是否三點共線
如果 3 個點連成一點線，則圍起來的三角形面積為 0
則直接判斷外積是否為 0 即可
```cpp=
bool collinearity(const Pt& a, const Pt& b, const Pt& c){
return (b-a)^(c-a) < EPS;
}
```
### 判斷點是否在線段上
必要條件為點與線段共線(外積為 0)
且 點往兩端點的方向會相反(內積為負)
```cpp=
bool inLine(const Pt& p, const Line& li){
return collinearity(li.st, li.ed, p) && (li.st-p)*(li.ed-p) < EPS;
}
```
----
### 判斷兩線段是否相交
如果相交則分成兩種 case
1. 交點在其中一個端點上
2. 交點不在端點上
第一種 case 直接判斷以下四種情況即可
- $\texttt{inLine(line1.st, line2)}$
- $\texttt{inLine(line1.ed, line2)}$
- $\texttt{inLine(line2.st, line1)}$
- $\texttt{inLine(line2.ed, line1)}$
----
第二種 case :交點不在端點上
圖會長成以下
呈現交叉情況
則點 A、B 會在線段 $\overline{CD}$相異側
則點 C、D 會在線段 $\overline{AB}$相異側
如果在相異側則外積相乘為負
$(\overrightarrow{AB}\times\overrightarrow{AC})(\overrightarrow{AB}\times\overrightarrow{AD}) <0$
$(\overrightarrow{CD}\times\overrightarrow{CA})(\overrightarrow{CD}\times\overrightarrow{CB}) <0$
----
## 點在多邊形內部
兩種判法
1. 若點在多邊形內，則選一個方向的射線出現會碰到奇數次邊
(需要特判點是否在多邊形的邊或頂點上)
並且選的射線隨機選，避免剛好交到多邊形的頂點上
2. 若點在凸多邊形內部，則點與多邊形上所有頂點 $P_1,P_2,...P_n$ 依序對於所有 $\overrightarrow{AP_i} \times \overrightarrow{AP_{i+1}}$ 皆為同號(全部都是正或者全部都是負的)
若有異號的情況則代表點在凸包外
若出現一個 0 則代表點在邊上，出現兩個 0 則代表點在頂點上
---
## 凸包
你有 $n$ 個點，然後你要找出一個凸多邊形可以圍住這n個點且面積最小，
這個凸多邊形稱為凸包
你也可以想成凸包是用一條橡皮筋把牆壁上的圖釘圈起來的範圍
----
----
## Andrew's Monotone Chain
(競賽常用的做法)
作法為分別求出上下凸包，求完之後再和再一起，
上半凸包+下半凸包=完整的凸包
----
先求下凸包
1. 先將全部點照 $x$ 大小排序,再排 $y$ 大小
2. 依序嘗試將點加入凸包判斷是否合法
3. 不合法刪掉前面最後一個點，合法則將點加進凸包
----
如何判斷合法
首先先觀察凸包，若我們從左到右依序看點，會發現下一個向量都是在前一個向量的逆時鐘方向
像是 $\overrightarrow{P_2 P_3}$ 會在 $\overrightarrow{P_2 P_4}$ 的逆時鐘方向
----
而 $\overrightarrow{P_{i} P_{i+1}}$ 若是在$\overrightarrow{P_{i} P_{i+2}}$ 的逆時鐘方向，則$\overrightarrow{P_{i} P_{i+1}} \times \overrightarrow{P_{i} P_{i+2}} > 0$
因此如果 $\overrightarrow{P_{i} P_{i+1}} \times \overrightarrow{P_{i} P_{i+2}} \le 0$ 代表前一個點會在凸包裡面，
而不會在凸包上，就可以把前一個點刪掉，再把新的點加進去凸包裡面
----
而實作可以用一個stack去維護，
一開始先把前兩個點直接加進去stack之後每一個點$P_i$都去判斷，
向量是不是往逆時針方向 ( $\overrightarrow{P_{i-2} P_{i-1}} \times \overrightarrow{P_{i-2} P_{i}} > 0$ )
若非法則把stack的top刪掉，一直刪到合法為止，
再把新的點加進去凸包
----
```cpp=
struct Pt{
int x,y;
Pt(){}
Pt(int _x,int _y){
x=_x,y=_y;
}
Pt operator-(const Pt &a){
return Pt(x-a.x, y-a.y);
}
bool operator<(const Pt &a) const {
return x < a.x || (x == a.x && y < a.y);
}
friend int cross(const Pt& o,const Pt& a,const Pt& b){
Pt lhs = o-a, rhs = o-b;
return lhs.x*rhs.y - lhs.y*rhs.x;
}
};
vector<Pt> convex_hull(vector<Pt> hull){
sort(hull.begin(),hull.end());
int top=0;
vector<Pt> stk;
for(int i=0;i<hull.size();i++){
while(top>=2&&cross(stk[top-2],stk[top-1],hull[i])<=0)
stk.pop_back(),top--;
stk.push_back(hull[i]);
top++;
}
for(int i=hull.size()-2,t=top+1;i>=0;i--){
while(top>=t&&cross(stk[top-2],stk[top-1],hull[i])<=0)
stk.pop_back(),top--;
stk.push_back(hull[i]);
top++;
}
stk.pop_back();
return stk;
}
```
排序 $O(NlgN)$ + 找凸包 $O(N)$
複雜度 $O(NlgN)$
---
## 旋轉卡尺
* 最遠點對
* 最大三角形
* 最大四角形
----
### 最遠點對
一群點當中，距離最遠的兩個點叫作「最遠點對」
觀察一下可以發現，因為凸包上所有的點是包圍所有點的多邊形，因此最遠的兩點一定是凸包的其中兩點。
因此我們在做最遠點對的時候要先做凸包，接著可以用旋轉卡尺的概念去找最遠點對
----
類似雙指針的概念
每次移動把一個指針往下移一格，另一個則不斷往下移動，直到最大為止
----
```cpp=
double FarthestPair(vector<Pt> arr){
double ret=0;
for(int i=0,j=i+1;i<arr.size();i++){
while(distance(i,j)<distance(i,(j+1)%arr.size())){
j=(j+1)%arr.size();
}
ret=max(ret,distance(i,j));
}
return ret;
}
```
複雜度 $O(NlgN)$
求出凸包 $O(NlgN)$ + 旋轉卡尺 $O(N)$
----
### 最大三角形
給一堆點，求其中三個點圍成的三角形面積最大
----
一樣用旋轉卡尺，窮舉每個點當定點，第二個點每次向下轉一格，
而第三個點就跟著轉到找到最大為止
複雜度 $O(N^2)$ 窮舉點對
----
### 最大四角形
給一堆點，求其中四個點圍成的四角形面積最大
作法：把四角形拆成兩個三角形，兩邊分別旋轉卡尺
----
複雜度 $O(N^2)$
---
## 掃描線
解決圖形的周長，面積總和等問題
----
在二維座標中，給定n個矩形，求出這些矩形覆蓋的面積總和
----
### 作法
先將矩形的y座標離散化並且把矩形拆成左界右界
掃描線由左至右掃過去
用線段樹維護區間
每次掃到一個邊界就計算答案並加減值
----
----
假設我們掃描線從x軸由左至右掃過去
----
在區間10~40加值
----
ans += 30 * (30-10)
(y軸覆蓋總和) * (掃描線現在位置-前一個位置)
在區間30-70加值
----
ans += 60 * (50-30)
(y軸覆蓋總和) * (掃描線現在位置-前一個位置)
在區間10-40減值
----
ans += 40 * (80-50)
(y軸覆蓋總和) * (掃描線現在位置-前一個位置)
在區間30-70減值
----
https://oi-wiki.org/geometry/scanning/
---
計算幾何是個噁心的單元
除了實作複雜還須調整浮點數，
常常程式寫對但因為浮點數誤差可能就要處理個半小時到幾個小時
但卻又是 ICPC 台灣區常見的題型一定要好好跟他混熟
並且有很多很噁心的內容沒交到有興趣的可以在自己去研究
https://cp-algorithms.com/#geometry
----
### Question Time and Practice
[Homework Link](https://vjudge.net/contest/497959)
提交期限到下星期三 6/8 23:59 截止
Google Drive
Gist
Clipboard
Sign in with Wallet
