相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1137
解题报告
不难发现每一个点应尽量向编号大的点连边
所以就只剩下$O(n)$条线段了,直接做半平面交就好
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const double EPS = 1e-6; int n, m, tot; vector<int> del[N]; struct Point{ double x, y; inline Point() { } inline Point(double _x, double _y):x(_x), y(_y) { } inline Point operator - (const Point &P) const { return Point(x - P.x, y - P.y); } inline Point operator + (const Point &P) { return Point(x + P.x, y + P.y); } inline Point operator * (double d) { return Point(x * d, y * d); } inline double operator * (const Point &P) { return x * P.y - y * P.x; } inline double len() { return sqrt(x * x + y * y); } }p[N]; struct Line{ Point a, b; double slope; inline Line() { } inline Line(const Point &_a, const Point &_b):a(_a), b(_b) { } inline bool operator < (const Line &L) const { return slope < L.slope; } inline Point intersect(const Line &L) { double s1 = (L.b - L.a) * (b - L.a); double s2 = (a - L.a) * (L.b - L.a); return a + (b - a) * (s2 / (s1 + s2)); } inline bool OnLeft(const Point &P) { return (b - a) * (P - a) > EPS; } }l[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void HalfPlaneIntersection(Line *arr, int &sz) { for (int i = 1; i <= sz; i++) { Point vec = arr[i].b - arr[i].a; arr[i].slope = atan2(vec.y, vec.x); } sort(arr + 1, arr + 1 + sz); int l = 1, r = 0; for (int i = 1; i <= sz; i++) { for (; l < r && !arr[i].OnLeft(arr[r].intersect(arr[r - 1])); r--); for (; l < r && !arr[i].OnLeft(arr[l].intersect(arr[l + 1])); l++); arr[++r] = arr[i]; } for (; l < r - 1 && !arr[l].OnLeft(arr[r].intersect(arr[r - 1])); r--); sz = 0; for (int i = l; i <= r; i++) { arr[++sz] = arr[i]; } arr[0] = arr[sz]; arr[sz + 1] = arr[1]; } int main() { n = read(); m = read(); for (int i = 1; i <= n; i++) { p[i].x = read(); p[i].y = read(); } for (int i = 1; i <= m; i++) { int x = read(), y = read(); del[min(x, y)].push_back(max(x, y)); } for (int i = 1; i < n; i++) { sort(del[i].begin(), del[i].end()); int to = n; while (!del[i].empty() && *--del[i].end() == to) { to--; del[i].pop_back(); } if (i == 1 && to == n) { printf("%.10lf", (p[1] - p[n]).len()); exit(0); } if (to > i) { l[++tot] = Line(p[to], p[i]); } } l[++tot] = Line(p[1], p[n]); HalfPlaneIntersection(l, tot); double ans = -(p[1] - p[n]).len(); Point last = l[1].intersect(l[0]); for (int i = 1; i <= tot; i++) { Point cur = l[i].intersect(l[i + 1]); ans += (cur - last).len(); last = cur; } printf("%.10lf\n", ans); return 0; }