学完模拟退火后开始搞这道题，搞了一下午最终搞到了80分，剩下的实在不知道怎么办了……
首先肯定是把有交点的线段划分到一个集合，然后对每一个集合求一遍凸包。
然后两两合并，如果新的凸包的周长更小，那必定合并。
但有可能三个或以上合并才更优，所以上述算法肯定不行。
这时候就要模拟退火了。
每次随机合并两个，如果更优，就合并；否则有概率合并。然后我在每一次降温之前又暴力的全扫一遍尝试两两合并。
模拟退火跑到2.9秒，我又写了个一个乱搞算法，借鉴了当时rk1的写法，每次随机两个合并，直到剩一个凸包，然后取过程中的最优解。这个再跑到3.95秒。
最终搞到了80。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define In inlinetypedef long long ll;typedef double db;const int INF = 0x3f3f3f3f;const db eps = 1e-13;const db DELTA = 0.99999;const int maxn = 505;inline ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}inline void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}In void MYFILE(){#ifndef mrclr freopen("fields.in", "r", stdin); freopen("fields.out", "w", stdout);#endif}int n;struct Point{ db x, y; Point operator + (const Point& oth)const { return (Point){x + oth.x, y + oth.y}; } Point operator - (const Point& oth)const { return (Point){x - oth.x, y - oth.y}; } db operator * (const Point& oth)const { return x * oth.y - y * oth.x; } friend In void swap(Point& A, Point& B) { swap(A.x, B.x), swap(A.y, B.y); } friend In db dis(Point& A, Point& B) { return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)); }};struct Line{ Point A, B; friend In bool cross(Line a, Line b) { db ret1 = ((a.B - a.A) * (b.A - a.A)) * ((a.B - a.A) * (b.B - a.A)); db ret2 = ((b.B - b.A) * (a.A - b.A)) * ((b.B - b.A) * (a.B - b.A)); return ret1 < 0 && ret2 < 0; }}l[maxn];int vis[maxn], cnt = 0;vector v[maxn];db S[maxn];Point a[maxn], P;int tot = 0, st[maxn], top = 0;In bool cmp(Point A, Point B) {return (A - P) * (B - P) > 0;}In db calc(){ int pos = 1; for(int i = 2; i <= tot; ++i) if(a[i].x < a[pos].x || (fabs(a[i].x - a[pos].x) < eps && a[i].y < a[pos].y)) pos = i; if(pos ^ 1) swap(a[1], a[pos]); P = a[1]; sort(a + 2, a + tot + 1, cmp); st[top = 1] = 1; for(int i = 2; i <= tot; ++i) { while(top > 1 && (a[i] - a[st[top - 1]]) * (a[st[top]] - a[st[top - 1]]) > 0) --top; st[++top] = i; } st[top + 1] = st[1]; db ret = 0; for(int i = 1; i <= top; ++i) ret += dis(a[st[i]], a[st[i + 1]]); return ret;}In db TIME() {return 1.0 * clock() / CLOCKS_PER_SEC;}vector v2[maxn];db S2[maxn], sum = 0, ans = 0;int id[maxn], cnt2 = 0;In void HIA(){ db T = n <= 60 ? 1000000000 : 10000000, ans2 = sum; cnt2 = 0; for(int i = 1; i <= cnt; ++i) if(vis[i] == i) id[++cnt2] = i; while(T > eps && cnt2 > 1) { if(TIME() > 2.8) return; int x = rand() % cnt2 + 1, y = rand() % cnt2 + 1; while(x == y) y = rand() % cnt2 + 1; if(x > y) swap(x, y); tot = 0; for(int i = 0; i < (int)v2[id[x]].size(); ++i) a[++tot] = v2[id[x]][i]; for(int i = 0; i < (int)v2[id[y]].size(); ++i) a[++tot] = v2[id[y]][i]; db tp = calc(), del = tp - S2[id[x]] - S2[id[y]]; if(del < 0 || exp(-del / T) * RAND_MAX > rand()) { ans2 = ans2 - S2[id[x]] - S2[id[y]] + tp; ans = min(ans, ans2); S2[id[x]] = tp; for(int i = 0; i < (int)v2[id[y]].size(); ++i) v2[id[x]].push_back(v2[id[y]][i]); for(int i = y + 1; i <= cnt2; ++i) id[i - 1] = id[i]; --cnt2; } for(int i = x + 1; i <= cnt2; ++i) { if(TIME() > 2.8) return; tot = 0; for(int j = 0; j < (int)v2[id[x]].size(); ++j) a[++tot] = v2[id[x]][j]; for(int j = 0; j < (int)v2[id[i]].size(); ++j) a[++tot] = v2[id[i]][j]; db tp = calc(); if(tp < S2[id[x]] + S2[id[i]]) { ans2 = ans2 - S2[id[x]] - S2[id[i]] + tp; ans = min(ans, ans2); S2[id[x]] = tp; for(int j = 0; j < (int)v2[id[i]].size(); ++j) v2[id[x]].push_back(v2[id[i]][j]); for(int j = i + 1; j <= cnt2; ++j) id[j - 1] = id[j]; --cnt2; } } T *= DELTA; }}In void HIA2(){ db ans2 = sum; cnt2 = 0; for(int i = 1; i <= cnt; ++i) if(vis[i] == i) id[++cnt2] = i; while(cnt2 > 1) { if(TIME() > 3.95) return; int x = rand() % cnt2 + 1, y = rand() % cnt2 + 1; while(x == y) y = rand() % cnt2 + 1; if(x > y) swap(x, y); tot = 0; for(int i = 0; i < (int)v2[id[x]].size(); ++i) a[++tot] = v2[id[x]][i]; for(int i = 0; i < (int)v2[id[y]].size(); ++i) a[++tot] = v2[id[y]][i]; db tp = calc(); ans2 = ans2 - S2[id[x]] - S2[id[y]] + tp; ans = min(ans, ans2); S2[id[x]] = tp; for(int i = 0; i < (int)v2[id[y]].size(); ++i) v2[id[x]].push_back(v2[id[y]][i]); for(int i = y + 1; i <= cnt2; ++i) id[i - 1] = id[i]; --cnt2; }}int main(){ //MYFILE(); srand(20010613); n = read(); for(int i = 1; i <= n; ++i) { Point A, B; A.x = read(), A.y = read(), B.x = read(), B.y = read(); l[i] = (Line){A, B}; } for(int i = 1; i <= n; ++i) if(!vis[i]) { vis[i] = 1; ++cnt; v[cnt].push_back(l[i].A), v[cnt].push_back(l[i].B); for(int j = i + 1; j <= n; ++j) if(!vis[j] && cross(l[i], l[j])) { vis[j] = 1; v[cnt].push_back(l[j].A), v[cnt].push_back(l[j].B); } } for(int i = 1; i <= cnt; ++i) { tot = 0; for(int j = 0; j < (int)v[i].size(); ++j) a[++tot] = v[i][j]; S[i] = calc(); } Mem(vis, 0); for(int i = 1; i <= cnt; ++i) if(!vis[i]) { vis[i] = i; for(int j = i + 1; j <= cnt; ++j) if(!vis[j]) { tot = 0; db tp; for(int k = 0; k < (int)v[i].size(); ++k) a[++tot] = v[i][k]; for(int k = 0; k < (int)v[j].size(); ++k) a[++tot] = v[j][k]; if((tp = calc()) < S[i] + S[j]) { S[i] = tp; vis[j] = i; for(int k = 0; k < (int)v[j].size(); ++k) v[i].push_back(v[j][k]); } } ans += S[i], sum += S[i]; } while(TIME() < 2.9) { for(int i = 1; i <= cnt; ++i) { v2[i].clear(); S2[i] = S[i]; for(int j = 0; j < (int)v[i].size(); ++j) v2[i].push_back(v[i][j]); } HIA(); } while(TIME() < 3.95) { for(int i = 1; i <= cnt; ++i) { v2[i].clear(); S2[i] = S[i]; for(int j = 0; j < (int)v[i].size(); ++j) v2[i].push_back(v[i][j]); } HIA2(); } printf("%.8lf\n", ans); return 0;}