绝地反击
有 (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
",r);
return 0;
}