绝地反击[JSOI 2018]

发表于 分类于 ，

题目链接

bzoj

暂时速度排rank4..

题目描述

一个平面直角坐标系上 $n$ 艘飞船，同时开始移动，需要移动到 $x^2+y^2=R^2$ 的圆中形成该圆的 $n$ 等分点。求飞船移动时间最大值的最小值，精度六位小数。

$n\leq 200$

题解

最大值最小，显然先二分答案 $W$。

这时候，每个飞船在 $W$ 的时间内，在这个圆上的能走到的点是一个连续的区间。

假设固定了这 $n$ 个等分点，那么就可以把飞船看做X集合，点看做Y集合，飞船 $i$ 能到点 $j$，则 $X_i$ 向 $Y_j$ 连一条边，做二分图最大匹配即可。

但是这个 $n$ 等分点可以随意旋转，似乎无法判断是否可行。

假设某种旋转角度是可行的，那么继续随意旋转，直到某个 $n$ 等分点和某个区间的边界重合，这时候点和飞船的配对还是一样的。

那么就说明，一种合法的情况中，会有至少一个点在某个区间的端点中。

这样的点至多有 $2n$ 个，对应着至多 $2n$ 个偏转角度。

一个十分显然的做法是，枚举这 $2n$ 个偏转角度，然后做二分图最大匹配。

这样的话，时间复杂度为 $O(n^3\sqrt n \log M)$，其中 $\log M$ 为二分的次数，大约在 $25$ 左右。

这样就会获得 $50pts$ 。

但是若用扫描线，从小到大枚举这 $2n$ 个偏转角度呢？

这样每次的状态和前面的状态相比，相当于减少或增加了一条边。

显然可以利用上一次网络流算的答案。

那么退流，至多修改三条边，再跑一遍网络流就好了。

一次退流再推一次的时间复杂度好像是 $O(n)$ 的。

时间复杂度 $O(不会证)$。

程序

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define db double
#define lb long db
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)

const int N=405;
const int M=100000;
const db Pi=acos(-1);
const db eps=1e-8;
const int inf=0x3f3f3f3f;
namespace G{
	int s,t;
	int val[M],ver[M],ne[M],head[N],cur[N],tot,d[N];
	inline void init()
	{
		fo(i,s,t) head[i]=cur[i]=0;
		tot=1;
	}
	inline void add(int x,int y,int z)
	{
		ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=0; ne[tot]=head[y]; head[y]=tot;
	}
	queue<int> que;
	inline bool bfs()
	{
		
		for(;!que.empty();que.pop());
		fo(i,s,t) d[i]=0;
		fo(i,s,t) cur[i]=head[i];
		d[s]=1;
		for(que.push(s);!que.empty();)
		{
			int u=que.front(); que.pop();
			for(int i=head[u],v;i;i=ne[i])
				if(!d[v=ver[i]]&&val[i])
				{
					d[v]=d[u]+1; que.push(v);
					if(v==t) return 1;
				}
		}
		return 0;
	}
	int dfs(int u,int flow)
	{
		if(u==t||flow==0) return flow;
		int res=flow,r;
		for(int &i=cur[u],v;i&&res;i=ne[i])
			if(d[v=ver[i]]==d[u]+1&&(r=dfs(v,min(res,val[i]))))
			{
				res-=r; val[i]-=r; val[i^1]+=r;
			}
		return flow-res;
	}
	void dinic(int &flow)
	{
		for(;bfs();flow+=dfs(s,inf));
	}
	inline void del(int x,int y,int &flow)
	{
		bool flag=0;
		for(int i=head[y],pre;i;pre=i,i=ne[i])
			if(ver[i]==x)
			{
				if(i==head[y]) head[y]=ne[i];
				else ne[pre]=ne[i];
				break;
			}
		for(int i=head[x],pre;i;pre=i,i=ne[i])
			if(ver[i]==y)
			{
				flag=(!val[i]);
				if(i==head[x]) head[x]=ne[i];
				else ne[pre]=ne[i];
				break;
			}
		if(!flag) return;
		flow--;
		for(int i=head[s];i;i=ne[i])
			if(ver[i]==x)
			{
				val[i]^=1; val[i^1]^=1;
				break;
			}
		for(int i=head[t];i;i=ne[i])
			if(ver[i]==y)
			{
				val[i]^=1; val[i^1]^=1;
				break;
			}
		if(bfs()) flow+=dfs(s,inf);
	}
	
}
using namespace G;
int n,m;
db K,x[N],y[N],rad;
struct node{
	db ang; int x,y,opt;
	friend inline bool operator<(const node &A,const node &B)
	{
		if(fabs(A.ang-B.ang)<eps) return A.opt>B.opt;
		return A.ang<B.ang;
	}
}q[N];
inline bool check(db W)
{
	m=0; init();
	db dis,l,r,ang,b;
	int L,R;
	fd(i,n,1) add(s,i,1),add(i+n,t,1);
	fo(i,1,n)
	{
		dis=sqrt(x[i]*x[i]+y[i]*y[i]);
		if(K+W<dis||dis<K-W) return 0;
		if(!(dis+K>W))
			fo(j,1,n) add(i,j+n,1);
		else
		{
			ang=atan2(x[i],y[i]);
			b=acos((dis*dis+K*K-W*W)/(dis*K*2));
			l=ang-b; r=ang+b;
			for(;l<0;l+=2*Pi);
			for(;r<0;r+=2*Pi);
			L=l/rad; R=r/rad; L++; R++;
			q[++m]=(node){l-rad*(L-1),i,L,1};
			q[++m]=(node){r-rad*(R-1),i,R,-1};
			if(l<=r) fo(j,L+1,R) add(i,j+n,1);
			else
			{
				fo(j,L+1,n) add(i,j+n,1);
				fd(j,R,1) add(i,j+n,1);
			}
		}
	}
	int flow=0;
	dinic(flow);
	if(flow>=n) return 1;
	sort(q+1,q+m+1);
	fo(i,1,m)
		if(q[i].opt==1)
		{
			add(q[i].x,q[i].y+n,1);
			if(bfs()) flow+=dfs(s,inf);
			if(flow>=n) return 1;
		}
		else del(q[i].x,q[i].y+n,flow);
	return 0;
}

int main()
{
	scanf("%d%lf",&n,&K);
	rad=2.0*Pi/n;
	fo(i,1,n) scanf("%lf%lf",&x[i],&y[i]);
	db l=0,r=282.8432,mid;
	s=0,t=2*n+1;
	for(;l+eps<r;)
	{
		mid=(l+r)/2.;
		if(check(mid)) r=mid;
		else l=mid;
	}
	printf("%.8lf",r);
	return 0;
}