【2023北京集训5】写作与沟通 做题记录

二维平面上有 $n$ 个点 $(x_i,y_i)$，有 $m$ 条无向边连接这些点。

你需要从某个点 $s$ 开始，不重不漏的经过所有边后回到 $s$，请最小化转过的角度之和，求最小的角度和。

注意最后要转回开始的方向。

保证所有点的度数都 $\le 4$。

$1\le n\le 10^5$，$n-1\le m\le 2n$，$0\le x_i,y_i\le 10^9$，保证图联通且不存在自环，保证存在欧拉回路。

设 $d_u$ 为 $u$ 的度数，显然 $d_u\in\{2,4\}$。

对于 $d_u=2$ 的点，在这里转过的角度是固定的，直接累加即可。

对于 $d_u=4$ 的点，相当于要给出边配对，一共只有三种不同的配对方法。那么先按照最优的方法配对，这样会形成若干个环，我们的目标就是调整配对方法使得最终只剩下一个环且代价最小。

接下来把环看成点，把调整后会合并的两个环连边，边权为调整的代价，跑最小生成树即可。

时间复杂度 $O(n\log n)$。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

#define fi first
#define se second

typedef long double db;

const db pi=acos(-1);

const int S=100005;

struct node
{
	int x,y;
};

struct edge
{
	int x,y;
	db w;
};

int n,m;
node a[S];
vector<pair<int,int> > g[S];
db b[S];
int fa[S*2];
int tot;
edge ed[S];

db cal(node a,node c,node b)
{
    db res=atan2(a.x-c.x,a.y-c.y)-atan2(b.x-c.x,b.y-c.y);
	if(res>pi) res-=pi*2;
	if(res<-pi) res+=pi*2;
	return pi-abs(res*180/pi)/(db)360*2*pi;
}

int fnd(int x)
{
	return fa[x]==x?x:fa[x]=fnd(fa[x]);
}

inline void meg(int x,int y)
{
	fa[fnd(x)]=fnd(y);
}

int main()
{
	freopen("write.in","r",stdin);
	freopen("write.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].emplace_back(y,i);
		g[y].emplace_back(x,i);
	}
	db ans=0;
	for(int i=1;i<=m;i++) fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		if(g[i].empty()) continue;
		if(g[i].size()==2)
		{
			int x=g[i][0].fi,xid=g[i][0].se;
			int y=g[i][1].fi,yid=g[i][1].se;
			ans+=cal(a[x],a[i],a[y]);
			meg(xid,yid);
		}
		else
		{
			db mn1=1e18,mn2=1e18;
			int id;
			for(int j=1;j<=3;j++)
			{
				int u=g[i][0].fi;
				int v=g[i][j].fi;
				int x,y;
				if(j==1) x=g[i][2].fi,y=g[i][3].fi;
				if(j==2) x=g[i][1].fi,y=g[i][3].fi;
				if(j==3) x=g[i][1].fi,y=g[i][2].fi;
				db pre=cal(a[u],a[i],a[v])+cal(a[x],a[i],a[y]);
				if(pre<mn1) mn2=mn1,mn1=pre,id=j;
				else if(pre<mn2) mn2=pre;
			}
			ans+=mn1;
			meg(g[i][0].se,g[i][id].se);
			int x,y;
			if(id==1) x=g[i][2].se,y=g[i][3].se;
			if(id==2) x=g[i][1].se,y=g[i][3].se;
			if(id==3) x=g[i][1].se,y=g[i][2].se;
			meg(x,y);
			b[i]=mn2-mn1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(g[i].size()<4) continue;
		int x=fnd(g[i][0].se),y=-1;
		for(auto t:g[i])
		{
			if(fnd(t.se)!=fnd(g[i][0].se)) y=fnd(t.se);
		}
		if(y!=-1) ed[++tot]=(edge){x,y,b[i]};
	}
	sort(ed+1,ed+tot+1,[&](edge x,edge y){
		return x.w<y.w;
	});
	for(int i=1;i<=tot;i++)
	{
		int x=ed[i].x,y=ed[i].y;
		db w=ed[i].w;
		if(fnd(x)==fnd(y)) continue;
		meg(x,y);
		ans+=w;
	}
	printf("%Lf\n",ans);
	return 0;
}