P3493 WSP-Island
调了很久，并发现了一些求半平面交的细节。
1.优雅地求两个直线的交点
考虑 \(l_1 : P_1 + k \times \vec{v_1}\) 和 \(l_2 : P_2 + t \times \vec{v_2}\) 的交点 \(O\)。假设 \(\vec{P_2O} = s \times \vec{v_2}\)。因为 \(O\) 也在 \(l_1\) 上，所以 \(\vec{P_1O} \times \vec{v_1} = 0\)，那么 \((\vec{P_1P_2} + \vec{P_2O}) \times \vec{v_1} = 0\)。拆开，带入，整理一下得 \(s = -\frac{\vec{P_1P_2} \times \vec{v_1}}{\vec{v_2} \times \vec{v_1}}\)。这个就非常好看了，然后把 \(s\) 带回去就行。
2.无穷交的情况不添加边界是没办法处理的
这个图就是一个反例，可以自己手模一下。那为什么按单调栈求上凸包的方法可以处理这种问题呢，这主要是由于斜率和极角的性质不同导致的。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long double ldb;
const int N = 1e5 + 5;
const ldb eps = 1e-12, pi = acos(-1);
int n, m, tot;
struct vec{ldb x, y;vec operator + (vec b){ return {x + b.x, y + b.y}; }vec operator - (vec b){ return {x - b.x, y - b.y}; }vec operator * (ldb k){ return {k * x, k * y}; }
}p[N];
ldb len(vec x){ return sqrt(x.x * x.x + x.y * x.y); }
ldb cross(vec a, vec b){ return a.x * b.y - a.y * b.x; }
struct line{vec P, v; ldb ang;void assign(vec p1, vec p2){ P = p1, v = p2 - p1, ang = atan2(v.y, v.x);}
}li[N];
vec inter(line a, line b){ldb t = -cross(b.P - a.P, a.v) / cross(b.v, a.v);return b.P + b.v * t;
}
int q[N], l = 1, r = 1;
bool right(vec a, line b){ return cross(a - b.P, b.v) >= 0; }
void solve(){sort(li + 1, li + 1 + tot, [](line a, line b){return ((fabs(a.ang - b.ang) < eps) ? (cross(b.v, a.P - b.P) >= 0) : a.ang < b.ang);});q[1] = 1;for(int i = 2; i <= tot; ++i){if(fabs(li[i].ang - li[i - 1].ang) < eps) continue;while(l < r && right(inter(li[q[r]], li[q[r - 1]]), li[i])) --r;while(l < r && right(inter(li[q[l]], li[q[l + 1]]), li[i])) ++l;q[++r] = i; }while(l < r && right(inter(li[q[r]], li[q[r - 1]]), li[q[l]])) r--;q[++r] = q[l];
}
vector<int> e[N];
int main(){cin.tie(nullptr)->sync_with_stdio(0);cin >> n >> m;for(int i = 1; i <= n; ++i){cin >> p[i].x >> p[i].y;}for(int i = 1; i <= m; ++i){int u, v;cin >> u >> v;if(u < v) swap(u, v);e[u].push_back(v);}for(int i = 1; i <= n; ++i){sort(e[i].begin(), e[i].end());int mex = 1;for(int j : e[i]){if(mex == j) ++mex;else break;}if(i == n && mex == 1) return cout << len(p[n] - p[1]) << '\n', 0;if(mex < i) li[++tot].assign(p[i], p[mex]);}li[++tot].assign(p[1], p[n]);solve();ldb ans = 0;vec lst = inter(li[q[l]], li[q[l + 1]]);for(int i = l + 1; i <= r - 1; ++i){vec tmp = inter(li[q[i]], li[q[i + 1]]);ans += len(tmp - lst);lst = tmp;}ans -= len(p[n] - p[1]) - len(lst - inter(li[q[l]], li[q[l + 1]]));cout << fixed << setprecision(10) << ans;return 0;
}