题解：
- 只要确定了每艘飞船的就位位置，就可以用二分+网络流求得答案；
- 定义偏转角度$a$为离$x$正半轴逆时针最近的边的弧度，$a \in [0,\frac{2\pi}{n})$
- 二分一个值，对于一个点可以求出可到达的弧度记为$[l,r]$
- 那么在$[0,a]$的移动范围内只有可能前面一个点删除，后面一个点加入；
- 对$O(n)$个关键点做网络流即可；
- 复杂度$O(n^4 \ logn)$
- 如果将关键点排序，每次只考虑变化的边退流可以优化到：$O(n^3 \log n)$
- View Code
?1 #include<bits/stdc++.h> ?2 #define ld double ?3 using namespace std; ?4 const int N=610,M=100010,inf=0x3f3f3f3f; ?5 const ld Pi=acos(-1),eps=1e-9; ?6 int n,S,T,vis[N],hd[N],o,cur[N],d[N],que[N],head,tail,flow,cnt; ?7 ld R,B; ?8 struct Edge{int v,nt,f;}E[M<<1]; ?9 struct poi{ld x,y;}p[N]; 10 ld dis(poi A){return sqrt(A.x*A.x+A.y*A.y);} 11 struct data{ 12 ????ld ang;int u,v,t; 13 ????data(ld _ang=0,int _u=0,int _v=0,int _t=0):ang(_ang),u(_u),v(_v),t(_t){}; 14 ????bool operator <(const data&A)const{return ang==A.ang?t>A.t:ang<A.ang;} 15 }q[N]; 16 bool bfs(){ 17 ????for(int i=S;i<=T;++i)vis[i]=0,cur[i]=hd[i]; 18 ????head=tail=0;vis[que[++tail]=S]=d[S]=1; ??19 ????while(head<tail){ 20 ????????int u=que[++head]; 21 ????????for(int i=hd[u];~i;i=E[i].nt)if(E[i].f){ 22 ????????????int v=E[i].v; 23 ????????????if(vis[v])continue; 24 ????????????vis[v]=1;d[v]=d[u]+1;que[++tail]=v; ?25 ????????????if(v==T)return true; 26 ????????} 27 ????} 28 ????return false; 29 } 30 int dfs(int u,int c){ 31 ????if(u==T||!c)return c; 32 ????int flow=0,f; 33 ????for(int i=cur[u];~i;i=E[i].nt){ 34 ????????int v=E[cur[u]=i].v; 35 ????????if(d[v]==d[u]+1&&(f=dfs(v,min(E[i].f,c)))){ 36 ????????????flow+=f;c-=f; 37 ????????????E[i].f-=f;E[i^1].f+=f; 38 ????????????if(!c)break; 39 ????????} 40 ????} 41 ????return flow; 42 } 43 void add(int u,int v){ 44 ????E[o]=(Edge){v,hd[u],1};hd[u]=o++; 45 ????E[o]=(Edge){u,hd[v],0};hd[v]=o++; 46 } 47 void del(int u,int v){ 48 ????int fg=0; 49 ????for(int i=hd[u];~i;i=E[i].nt)if(E[i].v==v){ 50 ????????if(!E[i].f)flow--;else fg=1; 51 ????????E[i].f=E[i^1].f=0; 52 ????????break; 53 ????} 54 ????if(fg)return; 55 ????for(int i=hd[S];~i;i=E[i].nt)if(E[i].v==u){ 56 ????????E[i].f=1;E[i^1].f=0;break; 57 ????} 58 ????for(int i=hd[v];~i;i=E[i].nt)if(E[i].v==T){ 59 ????????E[i].f=1;E[i^1].f=0;break; 60 ????} 61 ????if(bfs())flow+=dfs(S,inf); ?62 } 63 bool check(ld mid){ 64 ????flow=cnt=o=0; 65 ????for(int i=S;i<=T;++i)hd[i]=-1; 66 ????for(int i=1;i<=n;++i){ 67 ????????ld d=dis(p[i]); 68 ????????if(mid+d<=R||mid+R<=d)return false; 69 ????????if(R+d<=mid){ 70 ????????????for(int j=1;j<=n;++j)add(i,j+n); 71 ????????????continue; 72 ????????} 73 ????????ld ang=atan2(p[i].y,p[i].x); 74 ????????ld del=acos((d*d+R*R-mid*mid)/(2*d*R)); 75 ????????ld ang1=ang-del,ang2=ang+del; 76 ????????while(ang1<0)ang1+=Pi*2; 77 ????????while(ang2<0)ang2+=Pi*2; 78 ????????int l=ang1/B,r=ang2/B; 79 ????????ang1=ang1-B*l; 80 ????????ang2=ang2-B*r; 81 ????????l++;r++; 82 ????????q[++cnt]=(data){ang1,i,l,1}; 83 ????????q[++cnt]=(data){ang2,i,r,-1}; 84 ????????if(l<=r)for(int j=l+1;j<=r;++j)add(i,j+n); 85 ????????else { 86 ????????????for(int j=1;j<=r;++j)add(i,j+n); 87 ????????????for(int j=l+1;j<=n;++j)add(i,j+n); 88 ????????} 89 ????} 90 ????sort(q+1,q+cnt+1); 91 ????for(int i=1;i<=n;++i)add(S,i),add(i+n,T); 92 ????while(bfs())flow+=dfs(S,inf); 93 ????if(flow==n)return true; 94 ????for(int i=1;i<=cnt;++i){ 95 ????????if(~q[i].t){ 96 ????????????add(q[i].u,q[i].v+n); 97 ????????????if(bfs())flow+=dfs(S,inf); 98 ????????????if(flow==n)return true; 99 ????????}100 ????????else del(q[i].u,q[i].v+n);101 ????}102 ????return false;103 }104 int main(){105 ????#ifndef ONLINE_JUDGE106 ????freopen("P4518.in","r",stdin);107 ????freopen("P4518.out","w",stdout);108 ????#endif109 ????scanf("%d%lf",&n,&R);110 ????B=2*Pi/n;S=0,T=n*2+1;111 ????for(int i=1;i<=n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);112 ????ld l=0,r=200;113 ????while(r-l>eps){114 ????????ld mid=(l+r)/2;115 ????????if(check(mid))r=mid;116 ????????else l=mid;117 ????}118 ????printf("%.8lf\n",l+eps);119 ????return 0;120 }
LGP4518[JSOI2018]绝地反击
原文地址：https://www.cnblogs.com/Paul-Guderian/p/10410257.html