tags: tutorial
計算幾何＆其他
by FHVirus
閒聊時間
大綱
- 暖身題
- 一些基本的運算
- 凸包
- 多邊形面積
- 最遠點對
- 極角排序（Lawfung Sort）
- 線段相交
- 座標轉換
- 實作時間／一些不相關的題目
小約定
- 今天談的東西不是很嚴謹（講者爛）。
- 沒有特別指名的話都是在討論二維平面上的事。
暖身
水題大賽？
Naïve!
一些基本的運算
三角形、多邊形、凸多邊形、直角、面積
大家都會吧？
向量
以下是不嚴謹的簡單的介紹><
想像成箭頭／座標就對了啦ww
我們接下來會用到的東西
- 大多是二維向量
- 點積 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\) 為兩向量夾角。
叉積（外積）
常用在計算例舉之類的。
注意到，在二維平面的叉積常常直接取數值，
是因為叉積為三維的向量，且 \(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 優化。
怎麼做？
掃描、DQ一大堆⋯⋯
都不是今天要教的！
Andrew's Monotone Chain!
上下凸包分開找！
對於所有點按一軸排序，邊掃邊做事！
要怎麼判斷該不該加點？
還記得叉積嗎？
拿前兩點判斷！
複雜度
- sort \(O(n \log n)\)
- 掃描＋Stack 操作 均攤 \(O(n)\)
總複雜度 \(O(n \log n)\)！
扣的
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;
}
動態凸包什麼的之後再說
習題：
多邊形面積
大家應該都會算吧？
應該也不少人看過這個：
\[ \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)\)！
最遠點對
觀察一下不難發現，
最遠點對一定是凸包上的點對！
怎麼做？
\(O(n^2)\)？
Naïve!
\(O(n)\) ？
建凸包＋雙指針！
我們沿凸包逆時針進行，
對於遇到的每一個點，
其對應到的最遠點也只會逆時針走！
習題
- TIOJ 1105 PS3
- 給定 \(n\) 個點，求其所形成的最大三角形面積（\(n \leq 1500\)）
極角排序＆Lawfung Sort
\(O(n^3)\) ？
Naïve!
\(O(n^2 \log n)\) ？
枚舉每一個點，可以做什麼？
看他是不是直角那個點！
枚舉每個點當直角，
其他的點按照極角排序好，
雙指針掃過去！
（極角：從 x 軸開始逆時針走的夾角）
怎麼照極角排序？
還記得內外積嗎？
小優化 by warner1129
把第三、四象限的點以原點對稱過去！
線段相交
應該是本課最難搞的東西
給你平面上四個點 \(A, B, C, D\)，
求 \(\overline{AB}\) 與 \(\overline{CD}\) 有沒有相交？
重點
- 有沒有漏 case ？
- 好好判共線
想想看？
怎麼判斷一個點在不在簡單多邊形內部？
一個點隨便取一條射線，
若射線交簡單多邊形於奇數個點，
則在多邊形內！
怎麼做？
亂做！
不要中毒！
座標轉換
很重要
不要被 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 囉！