# 計算幾何 --- # 浮點數運算 ---- 不要用float，用double或long double 定義誤差為 $eps$，通常設 $eps=1e-9$ $a=0\Rightarrow abs(a)<eps$ $a=b\Rightarrow abs(a-b)<eps$ $a>b\Rightarrow a-b>eps$ $a\geq b\Rightarrow a-b>-eps$ --- # 三角函數向量複習 ---- ## 三角函數 $\pi = 180^\circ$ $tan\theta=\dfrac{sin\theta}{\cos\theta}$  $atan2(y,x)\in [-\pi,\pi]$ ---- ## 向量 表示方向與長度，也可代表座標（位置向量） $\vec{a}=(x_1,y_1),\ \vec{b}={x_2,y_2}$ 外積：$\vec{a}\times\vec{b}=|\vec{a}||\vec{b}|sin\theta=x_1y_2-y_1x_2$ 內積：$\vec{a}\cdot\vec{b}=|\vec{a}||\vec{b}|cos\theta=x_1x_2+y_1y_2$ 長度：$|\vec{a}|=\sqrt{\vec{a}\cdot\vec{a}}=\sqrt{x_1^2+y_1^2}$ 加減法：$\vec{a}\pm\vec{b}=(x_1\pm x_2,y_1\pm y_2$) ---- ## 儲存與運算 ```cpp! typedef long long ll; struct P{ ll x, y; P operator+(const P &rh)const {return P{x+rh.x,y+rh.y};} P operator-(const P &rh)const {return P{x-rh.x,y-rh.y};} ll operator*(const P &rh)const {return x*rh.x+y*rh.y;} //內積 ll operator^(const P &rh)const {return x*rh.y-y*rh.x;} //外積 double getangle(){return atan2(y,x);} ll lth2(){return x*x+y*y;} bool operator<(const P &rh)const {return x==rh.x?y<rh.y:x<rh.x;} void read(){scanf("%lld%lld",&x,&y);} }; ``` --- # 向量經典應用 ---- ## [CSES -- Point Location Test](https://cses.fi/problemset/task/2189) 給定三個點 $p_1,p_2,p_3$ ，若從 $p_1$ 往 $p_2$ 看， $p_3$ 在左側還是右側？或是 $p_3$ 在通過 $p_1,p_2$ 的直線上？ ---- $\theta\in[-\pi,0],sin\theta\geq0\Rightarrow外積可以用來判斷方向$ ```cpp! int ori(const P &a,const P &b,const P &c){ ll tmp = (b - a) ^ (c - a); //以a為基準，從b轉到c的方向 if (tmp == 0) return 0; return tmp < 0 ? -1 : 1; } ``` ---- ## [CSES -- Line Segment Intersection](https://cses.fi/problemset/task/2190) 給定線段 $\overline{AB}$ 與 $\overline{CD}$ ，求兩個線段是否有交點 提示：外積可以判斷方向 ---- 若兩段相交，可分為兩種情況  ---- - 交點在其中一個線段的端點 假設交點是點A $\Rightarrow ori(C,D,A)=0$ $cos\angle CAD\leq 0\Rightarrow \overrightarrow{AC}\cdot\overrightarrow{AD}\leq 0$ - 交點不再任一條的端點上 A,B在 $\overline{CD}$ 異側且 C,D在 $\overline{AB}$ 異側 ---- 程式碼： ```cpp! bool within(const P &a, const P &b, const P &c) { return (b - a) * (c - a) <= 0; } bool isits(const P &a, const P &b, const P &c, const P &d) { int abc = ori(a, b, c); int abd = ori(a, b, d); int cda = ori(c, d, a); int cdb = ori(c, d, b); if (!abc && !abd) return within(c, a, b) || within(d, a, b) || within(a, c, d) || within(b, c, d); return abc * abd <= 0 && cda * cdb <= 0; } ``` ---- ## 求交點座標：分點公式  $\overline{CP}:\overline{DP}=\triangle abc:\triangle abd=\overrightarrow{AB}\times\overrightarrow{AC}:-\overrightarrow{AB}\times\overrightarrow{AD}$ ---- 程式碼：型別改用double ```cpp! P itp(const P &a, const P &b, const P &c, const P &d) { double abc = (b - a) ^ (c - a); double abd = (b - a) ^ (d - a); return (d * abc - c * abd) / (abc - abd); } ``` ---- ## [CSES -- Polygon Area](https://cses.fi/problemset/task/2191) 依序給出一個多邊形的頂點，求多邊形面積的兩倍 提示：切成三角形算面積 ---- $\triangle=\dfrac{1}{2}absin\theta\Rightarrow外積$ 以一個頂點為基準，與剩下相鄰兩個依序求外積，就是答案 頂點順時針：負面積，頂點逆時針：正面積 基準點其實不需要頂點，其實就是測量師公式 ---- 程式碼：這份code點用pair存 ```cpp! #include <bits/stdc++.h> #define INF 0x3f3f3f3f #define eps 1e-9 #define F first #define S second #define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; pll operator-(pll a, pll b) { return pll(a.F - b.F, a.S - b.S); } llt operator^(pll a, pll b) { return a.F * b.S - a.S * b.F; } signed main() { int n; scanf("%d", &n); vector<pll> ar(n); for (int i = 0; i < n; i++) scanf("%lld%lld\n", &ar[i].F, &ar[i].S); llt ans = 0; for (int i = 2; i < n; i++) ans += (ar[i - 1] - ar[0]) ^ (ar[i] - ar[0]); printf("%lld\n", abs(ans)); } ``` --- # 掃描線 ----  ---- [TIOJ -- 矩形覆蓋面積計算](https://tioj.ck.tp.edu.tw/problems/1224) 給定一些矩形，求覆蓋的總面積（重疊僅算一次） 僅在意有變化出現的位置，也就是事件出現的時間 將橫向線段以y座標排序 分為矩形開始與矩形結束 可以用線段樹計算，每次紀錄當前y座標 --- # 極角排序 定從基準點出發的射線，以與射線的角度進行排序 - 方法一：atan2，較慢且若點非整數，有精度問題，但實作簡單推薦使用 - 方法二：外積，較快且不會有誤差，熟悉的話用外積更好 ---- 程式碼：atan2，象限順序 -- 三四一二 ```cpp! P bs={0,0}; //基準點座標 bool cmp(const P &a,const P &b){ return (a-bs).getangle() < (b-bs).getangle(); } signed main(){ vector<P> ar; sort(ar.begin(),ar.end(),cmp); } ``` ---- 程式碼：外積，象限順序 -- 一二三四 ```cpp! P bs={0,0}; //基準點座標 bool ud(const P &a){ //判上下半平面 if (!a.y)return a.x>0; return a.y>0; } bool cmp(P a, P b){ a=a-bs,b=b-bs; if (!a.x&&!a.y)return 1; if (!b.x&&!b.y)return 0; bool b1=ud(a),b2=ud(b); if (b1!=b2)return b1; return (a^b)>0; } signed main(){ vector<P> ar; sort(ar.begin(),ar.end(),cmp); } ``` ---- ## [TIOJ -- 直角三角形](https://tioj.ck.tp.edu.tw/problems/1205) 給定 $N$ 個點，求有多少組直角三角形？ $3\leq N\leq 1500$ 搭配技巧一：雙指針 ---- - 枚舉直角的點，將其他點極角排序 - 雙指針控制當前角度$\leq 90^\circ$ - 內積 $\geq0$，外積 > $0$ - 將相同角度合併起來較好算 ---- 程式碼： ```cpp! #include <bits/stdc++.h> // #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt") #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; // const int M = 998244353; // random_device rm; // mt19937 rg(rm()); // default_random_engine rg(rm()); // uniform_int_distribution<int> rd(INT_MIN, INT_MAX); // uniform_real_distribution<double> rd(0, M_PI); void db() { cerr << "\n"; } template <class T, class... U> void db(T a, U... b) { cerr << a << " ", db(b...); } template <typename T> void rd(T &x) { x = 0; bool f = 0; char c = getchar(); while (!isdigit(c)) f ^= !(c ^ 45), c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); f && (x = -x); } template <typename T> void prt(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) prt(x / 10); putchar((x % 10) ^ 48); } typedef long long ll; struct P { ll x, y; P operator+(const P &rh) const { return P{x + rh.x, y + rh.y}; } P operator-(const P &rh) const { return P{x - rh.x, y - rh.y}; } ll operator*(const P &rh) const { return x * rh.x + y * rh.y; } // 內積 ll operator^(const P &rh) const { return x * rh.y - y * rh.x; } // 外積 double getangle() const { return atan2(y, x); } ll lth2() { return x * x + y * y; } bool operator<(const P &rh) const { return x == rh.x ? y < rh.y : x < rh.x; } void read() { scanf("%lld%lld", &x, &y); } void prt() { printf("(%lld,%lld)", x, y); } }; int ori(const P &a, const P &b, const P &c) { ll tmp = (b - a) ^ (c - a); // 以a為基準，從b轉到c的方向 if (tmp == 0) return 0; return tmp < 0 ? -1 : 1; } bool within(const P &a, const P &b, const P &c) { return (b - a) * (c - a) <= 0; } bool isits(const P &a, const P &b, const P &c, const P &d) { int abc = ori(a, b, c); int abd = ori(a, b, d); int cda = ori(c, d, a); int cdb = ori(c, d, b); if (!abc && !abd) return within(c, a, b) || within(d, a, b) || within(a, c, d) || within(b, c, d); return abc * abd <= 0 && cda * cdb <= 0; } bool ud(const P &a) { // 判上下半平面 if (!a.y) return a.x > 0; return a.y > 0; } bool cmp(P a, P b) { bool b1 = ud(a), b2 = ud(b); if (b1 != b2) return b1; return (a ^ b) > 0; } const int N = 3505; P ar[N], br[N], ps[N]; int ns[N]; signed main() { int n; while (scanf("%d", &n) && n) { for (int i = 0; i < n; i++) ar[i].read(); llt ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) if (i != j) br[j - (j > i)] = ar[j] - ar[i]; sort(br, br + n - 1, cmp); int ln = 1; ns[0] = 1, ps[0] = br[0]; for (int j = 1; j < n - 1; j++) { if (br[j] ^ ps[ln - 1]) ps[ln] = br[j], ns[ln] = 1, ln++; else ns[ln - 1]++; } for (int j = 0; j < ln; j++) ns[j + ln] = ns[j], ps[j + ln] = ps[j]; for (int l = 0, r = 1; l < ln; l++, r = max(1, r - 1)) { if (r > 1 && !((ps[l] * ps[l + r - 1]))) ans += ns[l] * ns[l + r - 1]; while (r < ln && (ps[l] * ps[l + r]) >= 0 && (ps[l] ^ ps[l + r]) > 0) { if (!((ps[l] * ps[l + r]))) ans += ns[l] * ns[l + r]; r++; } } } printf("%lld\n", ans); } } ``` ---- ## [TIOJ -- 質感測試](https://tioj.ck.tp.edu.tw/problems/2191) 給定 $N$ 個有權重的點，有一條無限長通過原點的線，我們可以決定那條線的初始角度，並且將其旋轉一定角度，請問掃過的最大點權和是多少？ $1\leq N\leq 3\times 10^5$ 搭配技巧二：對稱 ---- - 掃過上半平面一部分，下半平面對稱部分也會掃到 - 可以將下半平面（含負x軸）點對稱原點 - 同個角度必須一起選，將其值合併起來 - 問題轉換成環狀區間連續最大和（greedy） ---- 程式碼： ```cpp! #include <bits/stdc++.h> #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; // const int M = 998244353; // random_device rm; // mt19937 rg(rm()); // default_random_engine rg(rm()); // uniform_int_distribution<int> rd(INT_MIN, INT_MAX); // uniform_real_distribution<double> rd(0, M_PI); void db() { cerr << "\n"; } template <class T, class... U> void db(T a, U... b) { cerr << a << " ", db(b...); } template <typename T> void rd(T &x) { x = 0; bool f = 0; char c = getchar(); while (!isdigit(c)) f ^= !(c ^ 45), c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); f && (x = -x); } template <typename T> void prt(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) prt(x / 10); putchar((x % 10) ^ 48); } typedef long long ll; struct P { ll x, y; P operator+(const P &rh) const { return P{x + rh.x, y + rh.y}; } P operator-(const P &rh) const { return P{x - rh.x, y - rh.y}; } ll operator*(const P &rh) const { return x * rh.x + y * rh.y; } // 內積 ll operator^(const P &rh) const { return x * rh.y - y * rh.x; } // 外積 double getangle() const { return atan2(y, x); } ll lth2() { return x * x + y * y; } bool operator<(const P &rh) const { return x == rh.x ? y < rh.y : x < rh.x; } void read() { scanf("%lld%lld", &x, &y); } void prt() { printf("(%lld,%lld)", x, y); } }; int ori(const P &a, const P &b, const P &c) { ll tmp = (b - a) ^ (c - a); // 以a為基準，從b轉到c的方向 if (tmp == 0) return 0; return tmp < 0 ? -1 : 1; } bool within(const P &a, const P &b, const P &c) { return (b - a) * (c - a) <= 0; } bool isits(const P &a, const P &b, const P &c, const P &d) { int abc = ori(a, b, c); int abd = ori(a, b, d); int cda = ori(c, d, a); int cdb = ori(c, d, b); if (!abc && !abd) return within(c, a, b) || within(d, a, b) || within(a, c, d) || within(b, c, d); return abc * abd <= 0 && cda * cdb <= 0; } bool cmp(P a, P b) { return (a ^ b) > 0; } const int N = 3e5 + 5; P ar[N]; int w[N], od[N]; signed main() { int n, sm = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { ar[i].read(), scanf("%d", &w[i]); if (ar[i].y < 0) ar[i].x = -ar[i].x, ar[i].y = -ar[i].y; if (!ar[i].y) ar[i].x = abs(ar[i].x); sm += w[i]; } iota(od, od + n, 0); sort(od, od + n, [&](int a, int b) { return cmp(ar[a], ar[b]); }); vector<int> vl; vl.pb(w[od[0]]); for (int i = 1; i < n; i++) { if (ar[od[i - 1]] ^ ar[od[i]]) vl.pb(w[od[i]]); else vl.back() += w[od[i]]; } int mx = 0, cx = 0, mn = 0, cn = 0; for (int x : vl) { cx = max(0, cx + x), tmax(mx, cx); cn = min(0, cn + x), tmin(mn, cn); } printf("%d\n", max(mx, sm - mn)); } ``` ---- ## [Atcoder -- Engines](https://atcoder.jp/contests/abc139/tasks/abc139_f) 給定一些向量，可以選其中一部分加起來，求加總起來最長的向量長度是多少？ 提示：反向的相加不好 ---- - 將向量極角排序，最好的一定是連續區間 - 可以用暴力或是雙指針 - 測資很強，可以檢驗模板的問題 ---- 程式碼： ```cpp! #include <cstdio> #include <stdio.h> #include <iostream> #include <math.h> #include <vector> #include <queue> #include <stack> #include <deque> #include <algorithm> #include <utility> #include <set> #include <map> #include <stdlib.h> #include <cstring> #include <string.h> #include <string> #include <sstream> #include <assert.h> #include <climits> #include <sstream> #include <numeric> #include <time.h> #include <limits.h> #include <list> #include <bitset> #include <unordered_map> #include <unordered_set> #include <random> #include <iomanip> #include <complex> #include <chrono> #include <fstream> #include <functional> // #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt") #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; // const int M = 998244353; // random_device rm; // mt19937 rg(rm()); // default_random_engine rg(rm()); // uniform_int_distribution<int> rd(INT_MIN, INT_MAX); // uniform_real_distribution<double> rd(0, M_PI); void db() { cerr << "\n"; } template <class T, class... U> void db(T a, U... b) { cerr << a << " ", db(b...); } template <typename T> void rd(T &x) { x = 0; bool f = 0; char c = getchar(); while (!isdigit(c)) f ^= !(c ^ 45), c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); f && (x = -x); } template <typename T> void prt(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) prt(x / 10); putchar((x % 10) ^ 48); } const int N = 2005; struct P { llt x, y; inline void sca() { scanf("%lld%lld", &x, &y); } inline llt lth2() const { return x * x + y * y; } P operator+(const P &rh) const { return P{x + rh.x, y + rh.y}; } P operator-(const P &rh) const { return P{x - rh.x, y - rh.y}; } llt operator^(const P &rh) const { return x * rh.y - y * rh.x; } } ar[N], cr; llt ans; bool ud(const P &a) { if (!a.y) return a.x > 0; return a.y > 0; } bool cmp(const P &a, const P &b) { int b1 = ud(a), b2 = ud(b); if (b1 ^ b2) return b1; return (a ^ b) > 0; } signed main() { int n; rd(n); for (int i = 0; i < n; i++) ar[i].sca(); for (int i = 0; i < n; i++) if (!ar[i].x && !ar[i].y) swap(ar[i--], ar[--n]); sort(ar, ar + n, cmp); for (int i = 0; i < n; i++) ar[i + n] = ar[i]; for (int l = 0, ln = 0; l < n; l++, ln--) { while (ln < n && (cr + ar[l + ln]).lth2() >= cr.lth2()) cr = cr + ar[l + ln++]; tmax(ans, cr.lth2()), cr = cr - ar[l]; } printf("%.15lf\n", sqrt(ans)); } ``` --- # 凸包 ---- 給定一些點，求覆蓋所有點的最小凸多邊形 - 頂點一定是給的點，不然可以再縮 - 凸包因為是凸多邊形，逆時針走都是往左轉  ---- 解法：掃描線加單調隊列 - 將點照字典序排好，依序遍歷 - 新點必須在當前凸包最後兩點左側，否則pop當前最後一點，直到符合加入新點  ---- - 將排序好的的點反轉，再做一次，就是另一面凸包（上凸包） - 最左最右兩點重複，可以在每一次蓋完半凸包，pop最後一點  ---- 程式碼： ```cpp! void fdhl(vector<P> &ar, vector<P> &hl, int lnar) { // ar點集,hl凸包頂點（逆時針）, lnar 點集大小 int lnhl; for (int i = 0; i < 2; i++) //蓋兩次 { int prln = hl.size(); //下凸包不能pop上凸包的點 for (int j = 0; j < lnar; j++) { lnhl = hl.size(); while (lnhl - prln > 1 && ori(hl[lnhl - 2], hl[lnhl - 1], ar[j]) <= 0) //等號看邊上的點需不需要留 { lnhl--; hl.pop_back(); } hl.push_back(ar[j]); } if (hl.size() > 1) hl.pop_back(); reverse(ar.begin(), ar.end()); //反轉 } if (hl.size() > 1 && hl.front() == hl.back()) hl.pop_back(); //特判一個點 } ``` ---- ## 練習題 裸凸包：https://tioj.ck.tp.edu.tw/problems/1178 凸包面積：https://tioj.ck.tp.edu.tw/problems/1280 凸包與多邊形面積差：https://tioj.ck.tp.edu.tw/problems/1678 ---- ## [Point in Polygon](https://cses.fi/problemset/task/2192) 給定一個多邊形，接下來有 $m$ 次詢問，每次詢問有一點，求該點是在多邊形內部外部還是邊界上？ ---- - 可以先用外積內積枚舉邊判斷邊界上 - 另一個很遠的點，枚舉所有邊和遠點與詢問點交點數量 - 每一次相交代表內外狀態更新一次（奇偶性） - 交點在頂點與共線可能會壞掉 - 多邊形給整數點，遠點x設大一點y比詢問點多一 - 與邊的交點就永遠不是整數點 ---- 程式碼： ```cpp! #include <bits/stdc++.h> #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; // const int M = 998244353; // random_device rm; // mt19937 rg(rm()); // default_random_engine rg(rm()); // uniform_int_distribution<int> rd(INT_MIN, INT_MAX); // uniform_real_distribution<double> rd(0, M_PI); void db() { cerr << "\n"; } template <class T, class... U> void db(T a, U... b) { cerr << a << " ", db(b...); } template <typename T> void rd(T &x) { x = 0; bool f = 0; char c = getchar(); while (!isdigit(c)) f ^= !(c ^ 45), c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); f && (x = -x); } template <typename T> void prt(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) prt(x / 10); putchar((x % 10) ^ 48); } typedef long long ll; struct P { ll x, y; P operator+(const P &rh) const { return P{x + rh.x, y + rh.y}; } P operator-(const P &rh) const { return P{x - rh.x, y - rh.y}; } ll operator*(const P &rh) const { return x * rh.x + y * rh.y; } // 內積 ll operator^(const P &rh) const { return x * rh.y - y * rh.x; } // 外積 double getangle() const { return atan2(y, x); } ll lth2() { return x * x + y * y; } bool operator<(const P &rh) const { return x == rh.x ? y < rh.y : x < rh.x; } void read() { scanf("%lld%lld", &x, &y); } void prt() { printf("(%lld,%lld)", x, y); } }; int ori(const P &a, const P &b, const P &c) { ll tmp = (b - a) ^ (c - a); // 以a為基準，從b轉到c的方向 if (tmp == 0) return 0; return tmp < 0 ? -1 : 1; } bool within(const P &a, const P &b, const P &c) { return (b - a) * (c - a) <= 0; } bool isits(const P &a, const P &b, const P &c, const P &d) { int abc = ori(a, b, c); int abd = ori(a, b, d); int cda = ori(c, d, a); int cdb = ori(c, d, b); if (!abc && !abd) return within(c, a, b) || within(d, a, b) || within(a, c, d) || within(b, c, d); return abc * abd <= 0 && cda * cdb <= 0; } bool cmp(P a, P b) { return (a ^ b) > 0; } const int N = 1005; P ar[N], p, pp; signed main() { int n, q; scanf("%d%d", &n, &q); for (int i = 0; i < n; i++) ar[i].read(); ar[n] = ar[0], pp.x = 1 << 31; while (q--) { p.read(), pp.y = p.y + 1; bool bl = 0; for (int i = 1; i <= n; i++) if (!ori(ar[i - 1], ar[i], p) && within(p, ar[i - 1], ar[i])) { bl = 1; break; } if (bl) { puts("BOUNDARY"); continue; } int sm = 0; for (int i = 1; i <= n; i++) if (isits(ar[i - 1], ar[i], p, pp)) sm++; if (sm & 1) puts("INSIDE"); else puts("OUTSIDE"); } } ``` ---- ## [TIOJ -- 約定](https://tioj.ck.tp.edu.tw/problems/1873) 逆時針給一個凸包，接下來有一些詢問，每筆詢問有一個點，求該點是否在凸包內 ---- - 因為是凸包，所以可以直接枚舉邊看方向 - 每次詢問花 O(n)，但有更好方法 - 找凸包一點為基準點，二分搜夾住詢問點 - 基準點與兩條邊夾住詢問點 - 看詢問點是否在這三角形內 - 輸入很奇怪，可以直接偷我寫的 ---- 程式碼： ```cpp! #include <cstdio> #include <stdio.h> #include <iostream> #include <math.h> #include <vector> #include <queue> #include <stack> #include <deque> #include <algorithm> #include <utility> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <stdlib.h> #include <string.h> #include <string> #include <sstream> #include <assert.h> #include <climits> #include <random> #include <numeric> #include <time.h> #include <limits.h> #include <list> #define F first #define S second #define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair<int, int> pii; typedef long long llt; const double eps = 1e-9; struct P { double x, y; P() {} P(double x, double y) : x(x), y(y) {} friend bool operator<(P a, P b) { return a.x == b.x ? a.y < b.y : a.x < b.x; } friend bool operator==(P a, P b) { return a.x == b.x && a.y == b.y; } P operator+(const P &b) const { return P(x + b.x, y + b.y); } P operator-(const P &b) const { return P(x - b.x, y - b.y); } P operator*(double b) const { return P(x * b, y * b); } P operator/(double b) const { return P(x / b, y / b); } double operator*(const P &b) const { return x * b.x + y * b.y; } double operator^(const P &b) const { return x * b.y - y * b.x; } double lth() { return sqrt(x * x + y * y); } }; int ori(P a, P b, P c) { double k = (b - a) ^ (c - a); if (-eps < k && k < eps) return 0; return k > 0 ? 1 : -1; } bool within(P a, P b, P c) { return (b - a) * (c - a) < eps; } bool its(P a, P b, P c, P d) { int abc = ori(a, b, c); int abd = ori(a, b, d); int cda = ori(c, d, a); int cdb = ori(c, d, b); if (!abc && !abd) return within(a, c, d) || within(b, c, d); return abc * abd <= 0 && cda * cdb <= 0; } vector<P> hl; int ln; bool in(P a, vector<P> &hl) { int ln = hl.size(); if (ln == 1) return a == hl[0]; if (ln == 2) return within(a, hl[0], hl[1]); int l = 1, r = ln - 1, m; while (r - l > 1) { m = (l + r) >> 1; if (ori(hl[0], a, hl[m]) < 0) l = m; else r = m; } return ori(hl[0], hl[l], a) >= 0 && ori(hl[l], hl[r], a) >= 0 && ori(hl[r], hl[0], a) >= 0; } int main() { AC; P p; while (cin >> p.x >> p.y) { hl.push_back(p); while (cin >> p.x >> p.y) hl.push_back(p); ln = hl.size(); cin.clear(); cin.ignore(1000, 'Z'); cout << ln << "\n"; while (cin >> p.x >> p.y) { cin.ignore(1000, 'Z'); if (in(p, hl)) cout << 'y' << '\n'; else cout << 'n' << '\n'; } cout << "\n"; cin.clear(); hl.clear(); cin.ignore(1000, 'Z'); } } ``` ---- ## 旋轉卡尺 -- 平面最遠點對  ---- - 找出凸包，最遠點對一定在凸包上 - 固定一條直線（連續兩點），再枚舉另一點 - 面積（高）函數是有峰值的，先小再大然後小 - 可以用雙指針，枚舉兩條線跟另一點（三分搜也可） ---- 程式碼： ```cpp! #include <cstdio> #include <stdio.h> #include <iostream> #include <math.h> #include <vector> #include <queue> #include <stack> #include <deque> #include <algorithm> #include <utility> #include <set> #include <map> #include <stdlib.h> #include <cstring> #include <string.h> #include <string> #include <sstream> #include <assert.h> #include <climits> #include <sstream> #include <numeric> #include <time.h> #include <limits.h> #include <list> #include <bitset> #include <unordered_map> #include <unordered_set> #include <random> // #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define lowbit(x) ((x) & -(x)) #define INF 0x3f3f3f3f #define eps 1e-9 #define F first #define S second #define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; // const int M = 998244353; // random_device rs; // // mt19937 rg(rs()); // default_random_engine rg(rs()); // uniform_int_distribution<int> rd(INT_MIN, INT_MAX); // uniform_real_distribution<double> rd(0, M_PI); pii operator-(pii a, pii b) { return pii(a.F - b.F, a.S - b.S); } int operator^(pii a, pii b) { return a.F * b.S - a.S * b.F; } int fdhl(vector<pii> &ar, vector<pii> &hl, int aln) { int psz, sz = 0; for (int t = 0; t < 2; t++) { psz = sz; for (int i = 0; i < aln; i++) { while (sz - psz > 1 && ((hl[sz - 1] - hl[sz - 2]) ^ (ar[i] - hl[sz - 2])) <= 0) hl.pop_back(), sz--; hl.push_back(ar[i]), sz++; } if (hl.size() > 1) hl.pop_back(), sz--; reverse(ar.begin(), ar.end()); } if (sz > 1 && hl.front() == hl.back()) hl.pop_back(), sz--; return sz; } int dst(pii a, pii b) { return (a.F - b.F) * (a.F - b.F) + (a.S - b.S) * (a.S - b.S); } int ar2(pii a, pii b, pii c) { return abs((b - a) ^ (c - a)); } signed main() { int n, ln, ans = 0; scanf("%d", &n); vector<pii> ar(n), hl; for (int i = 0; i < n; i++) scanf("%d%d", &ar[i].F, &ar[i].S); sort(ar.begin(), ar.end()); ln = fdhl(ar, hl, n); for (int i = 1, k = 1; i < ln; i++) { while (ar2(hl[i - 1], hl[i], hl[k]) < ar2(hl[i - 1], hl[i], hl[(k + 1) % ln])) (k += 1) %= ln; ans = max(max(dst(hl[i], hl[k]), dst(hl[i - 1], hl[k])), ans); } printf("%d\n", ans); } ``` ---- 最大三角形面積：https://zerojudge.tw/ShowProblem?problemid=b288 平面最遠點對：https://www.luogu.com.cn/problem/P1452 --- # 模擬退火 ---- - 隨機演算，尋找搜尋量很大的近似解 - 通常利用解會逐漸收斂的性質 - 沒頭緒也常常有人這樣亂做 ---- [TIOJ -- 生日快樂之炸飛洋鬼子](https://tioj.ck.tp.edu.tw/problems/1622) 順時針給定一凸多邊形，求內切圓半徑，誤差在0.01內算正確 ---- - 從多邊形內一點（重心）出發 - 設定步幅為 d ，隨機往一個方向走 - 若答案更好，則往那個方向走 - 將步幅縮小一定比例（0.9） - 重複走到步幅小於一定值 ---- 程式碼： ```cpp! #include <cstdio> #include <stdio.h> #include <iostream> #include <math.h> #include <vector> #include <queue> #include <stack> #include <deque> #include <algorithm> #include <utility> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <stdlib.h> #include <string.h> #include <string> #include <sstream> #include <assert.h> #include <random> #include <climits> #include <numeric> #include <time.h> #include <limits.h> #include <list> #include "lib1622.h" #define F first #define S second #define AC ios::sync_with_stdio(0), cin.tie(0) using namespace std; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef long long llt; const double PI = M_PI; const int MX = INT_MAX; const double eps = 1e-9; random_device rs; default_random_engine rg(rs()); uniform_real_distribution<double> rd(0, PI); pdd operator+(pdd a, pdd b) { return make_pair(a.F + b.F, a.S + b.S); } pdd operator-(pdd a, pdd b) { return make_pair(a.F - b.F, a.S - b.S); } double operator^(pdd a, pdd b) { return a.F * b.S - a.S * b.F; } double lth(pdd a) { return sqrt(a.F * a.F + a.S * a.S); } vector<pdd> ar; double ctr(pdd p) { double mn = MX; int ln = ar.size(); for (int i = 1; i < ln; i++) { mn = min(mn, ((ar[i] - p) ^ (ar[i - 1] - p)) / lth(ar[i - 1] - ar[i])); } return mn; } int main() { Initialize(); int n; double x, y, ans, d, ag, k; pdd p(0, 0); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lf%lf", &x, &y); ar.push_back(make_pair(x, y)); p.F += x, p.S += y; } p.F /= n, p.S /= n; ans = ctr(p), d = ans; assert(ans >= 0); while (d > eps) { ag = rd(rg); x = cos(ag) * d, y = sin(ag) * d; k = ctr(p + make_pair(x, y)); if (k > ans) { ans = k; p.F += x, p.S += y; } d *= 0.9; } Report(ans); } ``` --- # 題單 ### [Luogu 計算幾何從入門到跳樓](https://www.luogu.com.cn/training/16408) - 奇怪的題目不用寫