计算几何+欧拉回路合并：1222T2

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135152697

http://47.92.197.167:5283/contest/435/problem/2

2度点直接求夹角即可，4度角我是贪心选最小的情况。

但比如这样子：

在这里插入图片描述

我们会贪心选了4个蓝色角，形成红色和黄色两个欧拉回路，这就不是一个欧拉回路了。因此我们要考虑欧拉回路合并。

发现我们对于每个点划分成的两个集合各选一条边练一起，就可以合并两个欧=拉回路了。我们要使代价最小，相当于求以欧拉回路为点的最小生树。

1
2
3
4
5
preparing at 14:11
start coding at 14:13
start bugging at 14:28
finish bugging at 14:33
finish bloging aat 14:55
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 200010
#define pi acos(-1)
int n, m, i, j, k, T, u, v, c[N];

namespace Calc {
	struct Point {
		double x, y; 
	};	
	int calc_q(Point A) {
		if(A.x > 0 && A.y > 0) return 1; 
		if(A.x < 0 && A.y > 0) return 2; 
		if(A.x < 0 && A.y < 0) return 3; 
		if(A.x > 0 && A.y < 0) return 4; 
		if(A.x == 0 && A.y == 0) return 0; 
		if(A.x == 0) return -1; 
		if(A.y == 0 && A.x > 0) return -2; 
		if(A.y == 0 && A.x < 0) return -3; 
	}
	double calc_du(Point A) {
		if(A.x == 0) {
			if(A.y > 0) return pi/2; 
			else return 3*pi/2; 
		}
		if(A.y == 0) {
			if(A.x > 0) return 0; 
			else return pi; 
		}
		double k = A.y / A.x, t = atan(k); 
		int p = calc_q(A); 
		if(p == 2 || p == 3) t -= pi; 
		return t; 
	}
	double del(Point A, Point B, Point C) {
		Point AB = {B.x - A.x, B.y - A.y}; 
		Point BC = {C.x - B.x, C.y - B.y}; 
		double t1 = calc_du(AB); 
		double t2 = calc_du(BC);
		double d = t1 - t2; 
		while(d < 0) d += 2*pi; 
		while(d >= 2*pi) d -= 2*pi; 
		if(d > pi) d = 2*pi - d; 
		return d; 
	}
}
Calc :: Point a[N]; 
vector<pair<int, int> >G[N]; 

namespace Sol3 {
	double ans, t, sum, w[N]; 
	struct edge {
		int u, v; 
		double w; 
	}; 
	vector<edge>E; 
	int p1, p2, f[N]; 
	int fa(int x) {
		if(f[x] == x) return x; 
		return f[x] = fa(f[x]); 
	}
	pair<int, int>oth(int x) {
		if(x == 1) return {2, 3}; 
		if(x == 2) return {1, 3}; 
		if(x == 3) return {1, 2}; 
	}
	double cun(int i, int j) {
		double sum; 
		u = G[i][0].fi, v = G[i][j].fi; 
		sum = Calc::del(a[u], a[i], a[v]); 
		auto te = oth(j); 
		u = G[i][te.fi].fi, v = G[i][te.se].fi; 
		sum += Calc::del(a[u], a[i], a[v]); 
		return sum; 
	}
	void sol() {
		for(i=1; i<=m; ++i) f[i]=i; 
		for(i=1; i<=n; ++i) {
			if(c[i] <= 2) {
				u = G[i][0].fi, v = G[i][1].fi; 
				ans += Calc::del(a[u], a[i], a[v]); 
				f[fa(G[i][0].se)] = fa(G[i][1].se); 
			}
			else {
				w[i] = 1e9; t = 0; 
				for(j = 1; j <= 3; ++j) {
					sum = cun(i,  j); 
					if(sum < w[i]) w[i] = sum, t = j; 
				}
				ans += w[i]; 
				u = G[i][0].se; v = G[i][t].se; f[fa(u)] = fa(v); 
				auto te = oth(t); 
				u = G[i][te.fi].se, v = G[i][te.se].se; f[fa(u)] = fa(v); 
			}
		}
		for(i=1; i<=m; ++i) debug("%d ", fa(i)); debug("\n"); 
		for(i=1; i<=m; ++i) 
			if(c[i] > 2) {
				p1 = G[i][0].se; p1 = fa(p1); 
				for(j = 1; j <= 3; ++j) {
					p2 = G[i][j].se; p2 = fa(p2); 
					if(p1 == p2) continue; 
					sum = cun(i, j); 
					E.pb({p1, p2, sum - w[i]}); 
				}
			}
		sort(E.begin(), E.end(), [] (edge x, edge y) { return x.w < y.w; }); 
		for(auto t : E) if(fa(t.u) != fa(t.v)) f[fa(t.u)] = fa(t.v), ans += t.w; 
		printf("%.6lf", ans); 
	}
}

signed main()
{
	freopen("write.in", "r", stdin);
	freopen("write.out", "w", stdout);
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}	
	n=read(); m=read(); 
	for(i=1; i<=n; ++i)	scanf("%lf%lf", &a[i].x, &a[i].y); 
	for(i=1; i<=m; ++i) {
		u=read(); v=read(); ++c[u]; ++c[v]; 
		G[u].pb({v, i}); G[v].pb({u, i}); 
	}
	return Sol3 :: sol(), 0; 
	return 0;
}