有 \(n\) 个点 \((x_i, y_i)\)，你要把它们移动到一个半径为 \(R\)，圆心为原点的单位圆上，使得相邻两个点距离相同（即一个正 \(n\) 边形，每个顶点距离原点的距离都是 R）。最小化最大移动距离。
\(3 ≤ n ≤ 200\)。
https://www.cnblogs.com/hiweibolu/p/9048012.html
这道题的精髓在于两点：
枚举匹配可以每次旋转至卡着一段圆弧的边界。
网络流边数变化不大，所以可以暴力退流。
https://www.cnblogs.com/Paul-Guderian/p/10410257.html
CO int N=400+10,inf=1e9;namespace flow{ int n,S,T; struct edge {int v,c,a;}; vector<edge> to[N]; int dis[N]; void init(int n){ flow::n=n,S=n-1,T=n; for(int i=1;i<=n;++i) to[i].clear(); } IN void link(int u,int v,int c){ to[u].push_back({v,c}),to[v].push_back({u,0}); to[u].back().a=to[v].size()-1,to[v].back().a=to[u].size()-1; } bool bfs(){ fill(dis+1,dis+n+1,inf),dis[T]=0; deque<int> Q={T}; while(Q.size()){ int u=Q.front();Q.pop_front(); for(CO edge&e:to[u])if(to[e.v][e.a].c) if(dis[e.v]>dis[u]+1) dis[e.v]=dis[u]+1,Q.push_back(e.v); } return dis[S]<inf; } int dfs(int u,int lim){ if(u==T) return lim; int rest=lim; for(edge&e:to[u])if(e.c and dis[e.v]==dis[u]-1){ int delta=dfs(e.v,min(e.c,rest)); if(!delta) {dis[e.v]=inf;continue;} rest-=delta,e.c-=delta,to[e.v][e.a].c+=delta; if(!rest) break; } return lim-rest; } int erase(int u,int v){ bool flag=0; for(edge&e:to[u])if(e.v==v){ if(e.c) flag=1; e.c=to[e.v][e.a].c=0; break; } if(flag) return 0; for(edge&e:to[S])if(e.v==u){ e.c=1,to[e.v][e.a].c=0; break; } for(edge&e:to[v])if(e.v==T){ e.c=1,to[e.v][e.a].c=0; break; } return -1; }}CO float128 pi=acos(-1),eps=1e-9;int n;float128 R,B;struct point {float128 x,y;}p[N];struct event {float128 ang;int u,v,o;}q[N];bool check(float128 M){ flow::init(2*n+2); int tot=0; for(int i=1;i<=n;++i){ float128 D=sqrt(p[i].x*p[i].x+p[i].y*p[i].y)+eps; // edit 1: /0 if(M+D<=R or M+R<=D) return 0; // disjoint if(R+D<=M){ // contain for(int j=1;j<=n;++j) flow::link(i,j+n,1); continue; } float128 ang=atan2(p[i].y,p[i].x); float128 del=acos((D*D+R*R-M*M)/(2*D*R)); // edit 1: /0 float128 ang1=ang-del,ang2=ang+del; while(ang1<0) ang1+=2*pi; while(ang2<0) ang2+=2*pi; int l=ang1/B,r=ang2/B; // no coincidence ang1=ang1-l*B,ang2=ang2-r*B; ++l,++r; // convert to index q[++tot]={ang1,i,l,1},q[++tot]={ang2,i,r,-1}; if(l<=r){ for(int j=l+1;j<=r;++j) flow::link(i,j+n,1); } else{ for(int j=1;j<=r;++j) flow::link(i,j+n,1); for(int j=l+1;j<=n;++j) flow::link(i,j+n,1); } } for(int i=1;i<=n;++i) flow::link(flow::S,i,1),flow::link(i+n,flow::T,1); int ans=0; while(flow::bfs()) ans+=flow::dfs(flow::S,inf); if(ans==n) return 1; sort(q+1,q+tot+1,[](CO event&a,CO event&b)->bool{ return a.ang!=b.ang?a.ang<b.ang:a.o>b.o; }); for(int i=1;i<=tot;++i){ if(q[i].o==1) flow::link(q[i].u,q[i].v+n,1); else ans+=flow::erase(q[i].u,q[i].v+n); while(flow::bfs()) ans+=flow::dfs(flow::S,inf); if(ans==n) return 1; } return 0;}int main(){ read(n),scanf("%Lf",&R); B=2*pi/n; for(int i=1;i<=n;++i) scanf("%Lf%Lf",&p[i].x,&p[i].y); float128 l=0,r=200; while(r-l>eps){ float128 mid=(l+r)/2; if(check(mid)) r=mid; else l=mid; } printf("%.9Lf\n",r); return 0;}
