誤差分析

比如點的范圍是 \(w\)，那么斜率/極角誤差要到 \(w^{-2}\)。

比如 \(w=10^9\)，選取點 \((10^9,1)~(10^9-1,1)\)，就可以估算范圍是 \(\frac{1}{10^9-1}-\frac{1}{10^9}=\frac{1}{10^{18}}\)。

\(\operatorname{double}\) 最大 \(~2^{1024}\) 精度 \(10^{-15}\)
\(\operatorname{long double}\) 最大 \(~2^{2^{16}}\) 精度 \(10^{-18}\)

基本工具

點積 Dot

判斷角度，大于零為銳角，等于零為直角，小于零為鈍角。

同時可以判斷向量方向，正 OR 反。

求向量長度的時候，自己點積自己然后開方即可。

叉積 Cross

有向角 \(\theta\)，注意點積有交換律，叉積沒有。

可以判斷一些相對位置。

\(P_1\times P_2>0\)，\(P_2\) 在 \(P_1\) 逆時針方向。
\(P_1 \times P_2=0\)，共線，此時可以再用點積判斷同向還是異向。
\(P_1 \times P_2<0\)，\(P_2\) 在 \(P_1\) 順時針方向。

同時表示有向面積，逆時針面積為正。

極角排序

極角，\(\theta \in [-\pi,\pi)\)。

double 版本可以用函數(shù) atan2(y,x)，如果是 long double 版本就是 atan2l。

但是精度和速度不太好。于是這里可以用 cmp 函數(shù)，用叉積判斷逆時針和順時針。先判斷兩點在上下半邊的哪里，如果(y==0&&x<0)||y<0就是在下辦邊，反之在上半邊。如果在一邊的話用叉積判斷相對位置即可。

QOJ9503.Rikka with Triangles

給定平面上 \(n\) 個點，求所有銳角三角形的總面積，保證無三點共線，\(n\le 2000\)，\(|x_i|,|y_i|\le 10^{18}\)。

銳角三角形不好求，因為你需要滿足三個角都是銳角。但是很好判定直角三角形和鈍角三角形，所以統(tǒng)計這些三角形的面積，再拿總面積減去即可。

可以通過極角排序之后，雙指針統(tǒng)計貢獻(xiàn)。

P10671 BZOJ1278 向量 vector

雙倍經(jīng)驗：P5955 [POI 2018] Pionek。

凸包

給出一些點，求可以包含這些點的最小多邊形，即為凸包。

P2742【模板】二維凸包

二維凸包求法模板題。按照 \((x,y)\) 雙關(guān)鍵字升序排序后先求下凸殼，再求上凸殼。

先是循環(huán)從頭開始，每次不斷加點，同時用叉積判斷不合法的點彈出，求出下凸殼之后，從倒數(shù)第二個元素開始倒著循環(huán)，因為最后一個元素必然在求下凸殼的時候已經(jīng)加入了。對于第一個元素的處理就要注意了，由于其在上凸殼中也被加過了，所以直接的想法是倒著循環(huán)到最后不枚舉它了，但是這是錯的， 因為你在彈棧的時候可能會依賴這個點彈出若干不合法點，如果不枚舉它了就無法彈出不合法點了，正確做法是做完一遍之后彈出最后一個點，因為它必然被在開頭和結(jié)尾各加了一次。同時注意上凸殼彈棧的時候必須保留上凸殼的那些不能彈。

用點積判斷角度的時候，如果是嚴(yán)格凸包的話，等于要去掉。不嚴(yán)格的可以取等。

注意：如果有重點求不嚴(yán)格凸包會出問題，需要去重。

QOJ7906. Almost Convex

給定 \(n\) 個點，它們的凸包大小為 \(R\)。求有多少個大小 \(\le R+1\) 個點的簡單多邊形，包含所有點。滿足 \(n \le 2000\)，無三點共線。

先求出凸包，然后一個暴力做法就是枚舉每一個內(nèi)部的點，再枚舉每一條邊和其他的點判斷點是否在三角形內(nèi)即可，復(fù)雜度 \(O(n^3)\)。

考慮優(yōu)化，可以枚舉點再統(tǒng)計有多少邊符合要求，我們以該點為原點進(jìn)行極角排序，然后如果有凸包上的兩點在排序數(shù)組中相鄰，意味著枚舉點到凸包上那條邊之間無其他點，該邊合法。時間復(fù)雜度 \(O(n^2\log n)\)。

同樣可以枚舉邊，

發(fā)現(xiàn)對于某條邊，一個點合法當(dāng)且僅當(dāng)它們構(gòu)成的三角形內(nèi)部無點，考慮用角度刻畫，也就是不存在一個點兩個角都小于該點，這是一個二維偏序結(jié)構(gòu)，當(dāng)然不需要二維偏序來解。只需要對于一個角排序，另一個角查看是否為前綴最小值即可。時間復(fù)雜度 \(O(n^2\log n)\)

[ZROI 2019]

有 \(n\) 個點的圖，點有點權(quán) \(a_i\)，也有點權(quán) $b_i= \sum\limits_{j=1}^i a_j $。且 \(b_n=0\)?，F(xiàn)在從 \(1\) 點開始遍歷，經(jīng)過任意點后回到點 \(1\)。從 \(i\) 點到 \(j\) 的收益式子為 \(\frac{a_i-a_i}{2 \times a_i \times a_j} \times b_i \times b_j\)。并且遍歷時要求經(jīng)過點的 \(b\) 權(quán)值，在到達(dá)某個村莊之前是單調(diào)不降的，而之后又是單調(diào)不增的。求最大收益，保留五位小數(shù)。

我們發(fā)現(xiàn)收益式子很神秘，考慮拆開并且把相同下標(biāo)地放一起，得到

這是一個向量叉乘的結(jié)果，考慮平面上的 \(n\) 個點\((B_i,\frac{B_i}{A_i})\)，發(fā)現(xiàn)只需要維護(hù)一個凸包即可找到最優(yōu)路徑。

P10651 [ROI 2017] 虎

閔可夫斯基和

定義對于兩個點集 \(A,B\)，其閔可夫斯基和為 \(A+B=\{a+b,a\in A,b\in B\}\)。

我們研究兩個凸包之間的閔可夫斯基和，可以發(fā)現(xiàn)是把凸包中的邊進(jìn)行了平移得到的，等價于對于兩個凸包中的邊進(jìn)行極角排序之后放在一起。凸包本來就有單調(diào)性，所以可以直接歸并這些邊，復(fù)雜度是 \(O(|A|+|B|)\) 的。

具體做法就是初始點是 \(a_0+b_0\)，然后我們把凸包中的相鄰點作差分（得到了邊），按照斜率把種邊進(jìn)行歸并加入，每次都在上一個點的基礎(chǔ)上加上一個新加入的向量（邊）得到一個新的點。注意求完 Minkowski 之后最好再求一次凸包，去掉一次多余的點，比如三點共線之類的。

P4557 [JSOI2018] 戰(zhàn)爭

本題等價于對于 \(A\) 和 \((-B)\) 求閔可夫斯基和之后，判斷給定點是否在凸包之內(nèi)。

按照上文所述求出凸包之后，我們?nèi)我膺x擇一個點作為起點對于凸包進(jìn)行三角剖分。也就是通過該起點和凸包中任意兩個相鄰點，把凸包劃分為 \(n-2\) 個三角形。然后我們只需要通過叉積判斷方向，二分出給定點如果被凸包包含，會在哪個三角形之內(nèi)，然后再判斷是否在這個三角形之內(nèi)（直接用叉積對于第三條邊判定即可）。注意 corner case 就是可能出現(xiàn)某個點恰好處于最后一條邊上，特判一下即可。

雙倍經(jīng)驗：UVA10256 The Great Divide。

P8101 [USACO22JAN] Multiple Choice Test P

很牛的一道題目。

根據(jù) \(x^2\) 的凸性，可能成為答案的向量一定在其所處組的凸包上面。對于多個向量加法，那對應(yīng)的就是 Minkowski 和了。于是對于每一組向量建立凸包，把對于所有向量進(jìn)行 Minkowski 和，然后遍歷最后的凸包尋找最優(yōu)答案即可。

如果沒有想到第一步凸包怎么辦？我們可以從第二步那里反向推回去，沒反應(yīng)出第一步的凸包，但是看到向量的總和我們肯定會想到 Minkowski 和，然而這個時候我們會想到為了盡可能遠(yuǎn)離起點，所以這個點必須處于“最外面一層”，也就是 Minkowski 和之后的凸包上的點才是有用的點，所以我們需要對于每一組單獨(dú)建立凸包然后進(jìn)行 Minkowski 和。

如果快速對于多組向量求解 Minkowski 和？直接一個一個合并復(fù)雜度是錯的，因為單次的時間復(fù)雜度是 \(O(|A|+|B|)\)。一般對于這種復(fù)雜度的處理就是你按照 \(|A|\) 的大小從小往大一個一個合并就對了！參考 CF150E Freezing with Style 也是這種處理方法，和啟發(fā)式合并很像。當(dāng)然我們也可以分治求。

這里有一種更為高妙的方法，和兩個凸包求 Minkowski 和一樣，我們只要對于所有凸包中的所有邊都放在一起然后極角排序一下放入新的凸包就行了。

QOJ7929.Liquid Distribution

這是一些線性組合的形式，讓我們想到了向量。

因此考慮計算幾何，飲料混合就是向量加，故考慮 Minkowski 和。

混合飲料的過程就是縮小凸包的過程，

于是直接求出原始飲料的閔可夫斯基和，以及目標(biāo)飲料的閔可夫斯基和。判斷是否包含即可。

經(jīng)典問題

最近點對

KDT/分治/劃格子
枚舉 \(i \in[1,n]\)，設(shè) \(M\) 為目前最近點對的距離。

最小三角形

分治，先把點集按照中位數(shù)劃分為兩部分，然后分別求出兩邊的最小三角形。設(shè)目前最小的是 \(D\)，于是沿著中間線向兩邊分別延長 \(\frac{D}{2}\)，枚舉每一個點再向下枚舉 \(\frac{D}{2}\)。隨機(jī)情況下 \(\frac{D}{2}\) 的矩形內(nèi)點的個數(shù)為 \(O(1)\)。

ABC 234 Ex

劃分格子

APIO2018

香港2022

題意：求區(qū)間最近點對。
KDT和分治顯然不行。于是考慮劃格子，第 \(i\) 份格子的邊長為 \(2^{i+1}\)，于是范圍在 \([2^i,2^{i+1})\)，

ucup2 Delft B

給定 \(n\) 個點，在邊數(shù)為 \([3,k]\) 的路徑，中最小化 \(\max(d(p_i,p_{i+1}))\)，最小化的前提下求 \(k_{min}\)，最后再求滿足上述兩個條件的路徑個數(shù)。\(k \le30~n\le2\times 10^5\)
先求 \(k=3\) 的時候的答案，設(shè)為 \(M\)。
注意如果給的是點坐標(biāo)而非點點近距離，要多從幾何角度考慮。

ucup Delft H

給你 \(n\) 個點，有權(quán)值，要求找到一個矩形，滿足內(nèi)部點權(quán)值和-邊長最大。矩形不要求與坐標(biāo)軸平行。 n 400 8S

V圖

概念：給 \(n\) 個點，求出對于每個點，以它為最近點的區(qū)域。
求法1：對于每個點求出它與其他點的中垂線，然后再半平面交。
求法2：隨機(jī)切凸包

凸殼dp技巧

給 \(n\) 個點，求 \(5\) 個點的凸包的個數(shù)。
轉(zhuǎn)化求一個環(huán)使得斜率遞增。dp 狀態(tài)枚舉起點 \(s\)，邊 \((i,j)\) ，到的點個數(shù)，復(fù)雜度太大。可以對于 \(n^2\) 個點求向量，極角排序。枚舉向量， \(dp(s,t)\) 表示從 \(s\) 出發(fā)只經(jīng)過枚舉過的向量到達(dá) \(t\) 的方案數(shù)，對于邊 \((u,v)\) ，有 \(dp(s,u) \to dp(s,v)\)

Best Sun

快速點定位

離線從左往右掃描線，維護(hù)一下各平面上下順序。
在線，平衡樹樹 \(\to\) 可持久化平衡樹，\(O(n\log n)\)，難寫?？梢杂脴涮讟鋸?fù)雜度 \(O(n\log^2n)\)，本質(zhì)上求每個點最上面一條線是什么。

面積

求多邊形面積

1. 積分
2. \(\frac{1}{2}\sum(P_i \times P_{i+1})\)

圓交面積

圓交

余弦定理

求解

弓形+多邊形/格林公式（微積分）

辛普森積分

\(f(x)\) 表示圖形與 \(x=t\) 交線的長度。所以面積為 \(\int f(x)dx\)，不好直接積分?？梢越埔幌?。如果 \(f(x)\) 為三次以下多項式就可以近似為 \(\frac{1}{6}(r-l)(f(l)+f(r)+4f(\frac{l+r}{2}))\)。

圓上經(jīng)典問題

圓覆蓋點

平面上有 \(n\) 個點，找一個圓覆蓋其中 \(k\) 個點，問最小半徑。
二分答案 \(R\)，以每個點為圓心做一個半徑為 \(R\) 的圓，查找是否有區(qū)域被覆蓋了至少 \(k\) 次，區(qū)域查改為查圓弧交的次數(shù)。復(fù)雜度為 \(O(n^2\log n \log w)\)，可以進(jìn)一步優(yōu)化。可以對于枚舉每個圓單獨(dú)二分，考慮第 \(i\) 個圓之前的答案，先看看這個圓能否滿足，不過不滿足就取判斷下一個圓，如果滿足就說明這個圓可能更新最小答案，那就對前 \(i\) 個圓整體的二分一次。先隨機(jī)打亂圓，這樣每個圓可能更新答案的概率是 \(\frac{1}{i}\)，那么這一部分的期望復(fù)雜度就是 \(O(\sum\frac{1}{i}*i^2\log n\log w)\)。

PKUWC2018

求圓與一個簡單多邊形交的圓弧長度。

CF1446F Line Distance

經(jīng)典二分答案，然后判斷個數(shù)。然后需要以圓點為圓心畫一個 \(R\) 的圓。如果在園內(nèi)和圓上的點顯然對其他所有點連線距離滿足。園外兩點連線需要與圓相切或相交，考慮最極限的情況，

CCPC Guangzhou 2021 L

考慮 \(k_i=1\)，判斷點是否在凸包內(nèi)（求每一段直線，用叉積判斷點是否在兩段直線中間）。二分求切線即可。如果 \(k_i>1\)，

CF1019E Raining season

簡單多邊形點包含

1.在內(nèi)部/外部，作射線看有奇/偶個交點。
2.在邊上，枚舉邊。

WF2017A