Description：

给你 $n$ 个飞船的坐标，每单位时间可以移动一单位，要让他们移动到一个以 $(0,0)$ 为圆心的正多边形上，求最小距离。

$3\leqslant n\leqslant300$

Solution：

首先二分一个答案，那么每个点可以确定的范围是一个圆，这个圆与目标圆会有一段交（可能没有），如果我们直到这个多边形旋转的角度，我们就可以用网络流检查，但是现在我们不知道转角，但是会发现如果旋转目标圆，那么只有当一个点移出一个弧的端点的时候判定的值可能会发生变化，于是我们只有 $2n$ 个值要判断，需要跑 $2n\log n$ 次 $dinic$ 复杂度 $O(2n\log nn^2\sqrt n)$ 还是无法通过，考虑优化这个过程，合法的转角一共只有 $2n$ 个，我们把他们排序，那么不停旋转目标圆，每次会产生一个可行的匹配边或者加入一条边，如果每次重新构图复杂度还是爆炸，于是我们可以用增广和退流来模拟，加边就是增广一下这条边，删边就是把这个边的流量退掉。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

double R;

#define MAXN 310

const double PI = acos(-1),eps = 1e-8;

struct point

{

	double x,y;

}p[MAXN];

#define MAXE (MAXN * MAXN + 2 * MAXN)

#define MAXP (MAXN * 4)

struct edge

{

    int to,nxt,f;

}e[MAXE << 1];

int edgenum = 0;

int lin[MAXP] = {0};

void add(int a,int b,int f)

{//cout << a << " " << b << " " << f << endl;

    e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

    e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

    return;

}

int s,t;

#define INF 0x3f3f3f3f

int ch[MAXP];

bool BFS()

{

    memset(ch,-1,sizeof(ch));ch[s] = 0;

    queue<int> q;q.push(s);

    while(!q.empty())

    {

        int k = q.front();q.pop();

        for(int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(ch[e[i].to] == -1 && e[i].f)

            {

                ch[e[i].to] = ch[k] + 1;

                q.push(e[i].to);

            }

        }

    }

    return (ch[t] != -1);

}

int flow(int k,int f)

{

    if(k == t)return f;

    int r = 0;

    for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

    {

        if(ch[e[i].to] == ch[k] + 1 && e[i].f)

        {

            int l = flow(e[i].to,min(e[i].f,f - r));

            e[i].f -= l;r += l;e[i ^ 1].f += l;

        }

    }

    if(r == 0)ch[k] = -1;

    return r;

}

double alpha;

struct option{double d;int k,p,opt;}q[MAXN * 2];

int tot;

bool cmp(option a,option b){return (a.d != b.d ? a.d < b.d : a.opt > b.opt);}

void remove(int a,int b,int &ans)

{//cout << "remove " << a << " " << b << endl;

	int val = 0;

	for(int i = lin[b],j = 0;i != -1;j = i,i = e[i].nxt)

		if(e[i].to == a){j ? (e[j].nxt = e[i].nxt) : (lin[b] = e[i].nxt);break;}

	for(int i = lin[a],j = 0;i != -1;j = i,i = e[i].nxt)

		if(e[i].to == b){j ? (e[j].nxt = e[i].nxt) : (lin[a] = e[i].nxt);val = e[i].f ^ 1;break;}

	if(!val)return;--ans;

	for(int i = lin[s];i != -1;i = e[i].nxt)if(e[i].to == a){e[i].f ^= 1;e[i ^ 1].f ^= 1;break;}

	for(int i = lin[t];i != -1;i = e[i].nxt)if(e[i].to == b){e[i].f ^= 1;e[i ^ 1].f ^= 1;break;}

	if(BFS())ans += flow(s,INF);

	return;

}

bool check(double d)

{//cout << d << endl;

	memset(lin,-1,sizeof(lin));

	edgenum = 0;

	tot = 0;

	s = 0;t = 2 * n + 1;

	for(int i = 1;i <= n;++i)

	{

		double dis = sqrt(p[i].x * p[i].x + p[i].y * p[i].y);

		if(dis > R + d || dis < R - d)return false;

		if(dis + R <= d)for(int j = 1;j <= n;++j)add(i,j + n,1);

		else

		{

			double ang = atan2(p[i].y,p[i].x);

			double deg = acos((R * R + dis * dis - d * d) / (2 * R * dis));

			double l = ang - deg,r = ang + deg;

			while(l < 0)l += 2 * PI;while(r < 0)r += 2 * PI;

			int L = l / alpha,R = r / alpha;

			q[++tot] = (option){l - L * alpha,i,L + 1,1};

			q[++tot] = (option){r - R * alpha,i,R + 1,-1};

			++L;++R;

			if(l <= r)for(int j = L + 1;j <= R;++j)add(i,j + n,1);

			else

			{

				for(int j = L + 1;j <= n;++j)add(i,j + n,1);

				for(int j = 1;j <= R;++j)add(i,j + n,1);

			}

		}

	}

	for(int i = 1;i <= n;++i)add(s,i,1),add(i + n,t,1);

	sort(q + 1,q + 1 + tot,cmp);

	//for(int i = 1;i <= tot;++i)cout << q[i].d << " " << q[i].k << " " << q[i].p << " " << q[i].opt << endl;

	int ans = 0;

	while(BFS())ans += flow(s,INF);

	if(ans == n)return true;

	for(int i = 1;i <= tot;++i)

	{

		if(q[i].opt == 1)

		{

			add(q[i].k,q[i].p + n,1);

			if(BFS())ans += flow(s,INF);

			if(ans == n)return true;

		}

		else remove(q[i].k,q[i].p + n,ans);

	}

	return false;

}

int main()

{

	scanf("%d%lf",&n,&R);

	alpha = 2 * PI / n;

	for(int i = 1;i <= n;++i)p[i].x = rd(),p[i].y = rd();

	double l = 0,r = 400,mid;

	while(r - l > eps)

	{

		mid = (l + r) / 2;

		if(check(mid))r = mid;

		else l = mid;

	}

	printf("%.8lf\n",l);

	return 0;

}