###### tags: `tutorial`

# 計算幾何＆其他

by `FHVirus`

----

# 閒聊時間

<iframe width="560" height="315" src="https://www.youtube.com/embed/aLy9rRJ0ApU" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

---

# 大綱

----

- 暖身題
- 一些基本的運算
- 凸包
- 多邊形面積
- 最遠點對
- 極角排序（Lawfung Sort）
- 線段相交
- 座標轉換
- 實作時間／一些不相關的題目

----

## 小約定

1. 今天談的東西不是很嚴謹（講者爛）。
2. 沒有特別指名的話都是在討論二維平面上的事。

---

# 暖身

水題大賽？

----

[CF270A](http://codeforces.com/problemset/problem/270/A)

----

[CF1156A](https://codeforces.com/problemset/problem/1156/A)

----

[CF1096C](https://codeforces.com/problemset/problem/1096/C)

----

[CF195D](https://codeforces.com/problemset/problem/195/D)

----

Naïve!

---

# 一些基本的運算

----

三角形、多邊形、凸多邊形、直角、面積

大家都會吧？

----

## 向量

以下是不嚴謹的簡單的介紹><

----

### 想像成箭頭／座標就對了啦ww

<iframe width="560" height="315" src="https://www.youtube.com/embed/fNk_zzaMoSs?start=94" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

----

### 我們接下來會用到的東西

- 大多是二維向量
- 點積 Dot
- 叉積 Cross
- 相加相減（Naïve）

----

### 點積（內積）

大概可以描述兩個向量的方向有多一致。
運算方式：$a \cdot b = a_1 \cdot b_1 + a_2 \cdot b_2 \cdots$

----

對於兩個平面的向量：
- 若方向相同：$a \cdot b = |a||b|$
- 若兩者垂直：$a \cdot b = 0$
- 若方向相反：$a \cdot b = -|a||b|$
- 一般定義：$a \cdot b = |a||b| \cos \theta$，其中 $\theta$ 為兩向量夾角。

----

### [叉積（外積）](https://zh.wikipedia.org/wiki/叉积#/media/File:Cross_product_vector.svg)

常用在計算例舉之類的。
注意到，在二維平面的叉積常常直接取數值，
是因為叉積為三維的向量，且 $a \times b$ 會垂直 $a, b$（垂直平面），運算時多當成數值回傳。

----

計算方式：
對於二維的向量而言，
$a \times b = a_x \cdot b_y - a_y \cdot b_x$，
注意這會帶正負號。

手算的話也可以以 $a \times b = |a||b| \sin \theta$ 計算。

----

### 這可以幹嘛？

判斷兩個向量的夾角！

---

# 凸包 Convex Hull

別擔心，這裡沒有 DP 優化。

----

## 凸包是啥？

> 「凸」的定義是：圖形內任意兩點的連線不會經過圖形外部。
> by [演算法筆記](http://web.ntnu.edu.tw/~algo/ConvexHull.html)

簡單來說，一群點形成的凸包，就是周長最小且包住所有點的殼！

----


----

## 怎麼做？

----

掃描、DQ一大堆⋯⋯

都不是今天要教的！

----

## Andrew's Monotone Chain!

上下凸包分開找！

----

對於所有點按一軸排序，邊掃邊做事！


----

## 要怎麼判斷該不該加點？

還記得叉積嗎？

----

### 拿前兩點判斷！

----

### 複雜度

- sort $O(n \log n)$
- 掃描＋Stack 操作 均攤 $O(n)$

總複雜度 $O(n \log n)$！

----

### [例題：TIOJ 1178 Convex Hull](https://tioj.ck.tp.edu.tw/problems/1178)

----

### 扣的

struct point{
	ll x, y;
	point(){}
	point(ll x, ll y): x(x), y(y){}
	// 不會用到加法就不做了
	point operator-(point p){
		return point(x - p.x, y - p.y);
	}
	// Dot Product
	ll operator*(point p){
		return x * p.x + y * p.y;
	}
	// Cross Product
	// 注意運算子優先度！
	ll operator^(point p){
		return x * p.y - y * p.x;
	}
};

----

### 扣的

// All points, lower convex, upper convex
int n;
point p[N], lc[N], uc[N];
int lcp, ucp;

int32_t main(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    FOR(i,n){
        int a, b; cin >> a >> b;
        p[i] = {a, b};
    }
    sort(p, p + n, [](point a, point b){
        return a.x < b.x;
    });
    FOR(i,n){
        while(ucp > 1 and
            ((p[i] - uc[ucp - 2]) ^ (uc[ucp - 1] - uc[ucp - 2])) >= 0)
            --ucp;
        while(lcp > 1 and
            ((p[i] - lc[lcp - 2]) ^ (lc[lcp - 1] - lc[lcp - 2])) <= 0)
            --lcp;
        uc[ucp++] = p[i];
        lc[lcp++] = p[i];
    }
    // 凸包最左最右會重複算到
    cout << ucp + lcp - 2 << '\n';
    return 0;
}

----

動態凸包什麼的之後再說

----

### 習題：

- [TIOJ 1371 賢狼之網](https://tioj.ck.tp.edu.tw/problems/1371)

---

# 多邊形面積

----

大家應該都會算吧？

----

應該也不少人看過這個：

$$
\begin{align}
& \frac{1}{2}
\begin{vmatrix}
x_1 & x_2 & x_3 & \cdots \\
y_1 & y_2 & y_3 & \cdots
\end{vmatrix} \\
= & (x_1 \cdot y_2 - y_1 \cdot x_2) + \cdots + (x_n \cdot y_1 - y_n \cdot x_1) \\
= & v_1 \times v_2 + v_2 \times v_3 + \cdots + v_n \times v_1
\end{align}
$$

----

這東西對於所有多邊形都可以用！
按照逆時針排序點，
順時針的話就取個負號，
複雜度 $O(n)$！

----

### 就醬，丟題

- [TIOJ 1280 領土 (Territory)](https://tioj.ck.tp.edu.tw/problems/1280)
- [TIOJ 1159 房間面積計算](https://tioj.ck.tp.edu.tw/problems/1159)
- [Zerojudge d546 剪多邊形](https://zerojudge.tw/ShowProblem?problemid=d546)

---

# 最遠點對

----

觀察一下不難發現，
最遠點對一定是凸包上的點對！

怎麼做？

----

### $O(n^2)$？

Naïve!

----

### $O(n)$ ？

----

### 建凸包＋雙指針！

我們沿凸包逆時針進行，
對於遇到的每一個點，
其對應到的最遠點也只會逆時針走！

----


----

### 習題
- [TIOJ 1105 PS3](https://tioj.ck.tp.edu.tw/problems/1105)
- 給定 $n$ 個點，求其所形成的最大三角形面積（$n \leq 1500$）

---

# 極角排序＆Lawfung Sort

----

[例題：TIOJ 1205 直角三角形](https://tioj.ck.tp.edu.tw/problems/1205)

----

### $O(n^3)$ ？

Naïve!

----

### $O(n^2 \log n)$ ？

----

### 枚舉每一個點，可以做什麼？

----

### 看他是不是直角那個點！

----

枚舉每個點當直角，
其他的點按照極角排序好，
雙指針掃過去！

（極角：從 x 軸開始逆時針走的夾角）

----

### 怎麼照極角排序？

還記得內外積嗎？

----

[Lawfung Sort](http://alltherightcodes.blogspot.com/2016/08/tioj-1205.html)

----

### 小優化 by `warner1129`

把第三、四象限的點以原點對稱過去！

----

### 習題
- [AtCoder ABC 139F](https://atcoder.jp/contests/abc139/tasks/abc139_f)

---

# 線段相交

應該是本課最難搞的東西

----

給你平面上四個點 $A, B, C, D$，
求 $\overline{AB}$ 與 $\overline{CD}$ 有沒有相交？

----

### 重點
- 有沒有漏 case ？
- 好好判共線

----

想想看？

----


----

[例題：TIOJ 1876 回家](https://tioj.ck.tp.edu.tw/problems/1876)

----

怎麼判斷一個點在不在簡單多邊形內部？

----

一個點隨便取一條射線，
若射線交簡單多邊形於奇數個點，
則在多邊形內！

----

[例題：TIOJ 1423 直線線段相交問題 (Intersection)](w)

----

怎麼做？

----

亂做！
不要中毒！

---

# 座標轉換

很重要

----

例題：[IOI 2007 Pairs](https://tioj.ck.tp.edu.tw/problems/1345)

不要被 IOI 嚇到啦w
這題不難？

----

### 一維？

還算簡單吧？

----

### 二維？

- 枚舉每一對
- TLE

----

從頭想，觀察一下！

提示：平面距離有分三種。
對於兩個點 $i, j$，他們的距離：
- 歐幾里德：$\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$
- 曼哈頓（計程車幾何）：$|x_i - x_j| + |y_i - y_j|$
- 切比雪夫：$\max(|x_i - x_j|, |y_i - y_j|)$

----

可以發現，如果題目要求的是切比雪夫的話，就可以用區間資料結構掃過去！

但是，要怎麼做？

----


----

展開過程，
如果你上課的時候還看到這邊，
代表 `FHVirus` 沒做完講義，
她會負責現場導一次的。

----

這個技巧在二維可以把曼哈頓轉成切比雪夫！

----

三維也用一樣的技巧，
只不過你的式子會有四個維度！

----

### $\color{green}{AC}$

恭喜你會一題 IOI 囉！

----

### [為什麼很重要？](https://nhspc.csie.ntnu.edu.tw/wp-content/uploads/2020/11/109學年度資訊學科能力競賽決賽試題.pdf)

---

# 實作時間／雜題大戰

----

[ARC113 D](https://atcoder.jp/contests/arc113/tasks/arc113_d)

----