「JSOI2018」绝地反击
传送门
题解
明显是二分答案.
首先考虑每一个点在一个时间内能够到达的点是一个圆,那么如果圆和大圆相离,显然不行.
现在考虑有交,你取的一定是两个端点中的一个,接着你就可以发现这个东西可以网络流.
唯一的问题在于,你需要考虑这段区间外要把这个匹配删除,那么可以考虑模拟退流的过程.
代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<iostream>
#include<set>
#include<map>
using namespace std;
#define mp make_pair
#define ll long long
#define re register
typedef pair<int,int> pii;
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
int f=1,sum=0;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
const int N=5010,Inf = 1e9+10;
const double Pi=acos(-1.0),eps=1e-8;
int n,R,x[N],y[N],Q;
double nd;
struct node{int to,nxt,w;}e[N*N<<2];
struct ques{int u,v,opt;double ang;}q[N];
int front[N], cnt, s, t, dep[N] ;
void Add(int u,int v,int w)
{
e[cnt]=(node){v,front[u],w};front[u]=cnt++;
e[cnt]=(node){u,front[v],0};front[v]=cnt++;
}
bool cmp(ques a, ques b){return a.ang == b.ang ? a.opt > b.opt : a.ang < b.ang;}
queue<int>Que;
bool bfs()
{
memset(dep, 0, sizeof(dep)); dep[s] = 1; Que.push(s);
while(!Que.empty())
{
int u = Que.front(); Que.pop();
for(int i = front[u]; ~i; i = e[i].nxt)
{
int v = e[i].to;
if(e[i].w && !dep[v])
{
dep[v] = dep[u] + 1;
Que.push(v);
}
}
}
return dep[t];
}
int dfs(int u, int flow)
{
if(u==t||!flow) return flow;
for(int i=front[u];~i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].w&&dep[v]==dep[u]+1)
{
int di=dfs(v, min(flow, e[i].w));
if(di){e[i].w-=di;e[i^1].w+=di;return di; }
else dep[v] = -1;
}
}
return 0;
}
void del(int u,int v,int &ans)
{
int val=0;
for(int j=0,i=front[v];i;j=i,i=e[i].nxt)
if(e[i].to==u)
{
j?(e[j].nxt=e[i].nxt):(front[v]=e[i].nxt);
break;
}
for(int j=0,i=front[u];i;j=i,i=e[i].nxt)
if(e[i].to==v)
{
j?(e[j].nxt=e[i].nxt):(front[u]=e[i].nxt);val=e[i].w^1;
break;
}
if(!val)return;--ans;
for(int i=front[s];i;i=e[i].nxt)if(e[i].to==u){e[i].w^=1,e[i^1].w^=1;break;}
for(int i=front[t];i;i=e[i].nxt)if(e[i].to==v){e[i].w^=1,e[i^1].w^=1;break;}
if(bfs())ans+=dfs(s,Inf);
}
bool check(double mid)
{
memset(front,-1,sizeof(front));cnt=0;Q=0;
for(int i=1;i<=n;i++)Add(s,i,1),Add(i+n,t,1);
for(int i=1;i<=n;i++)
{
double dis=sqrt(x[i]*x[i]+y[i]*y[i]);
if(dis>mid+R||dis<R-mid)return false;
if(dis+R<=mid)
{
for(int j=1;j<=n;j++)Add(i,j+n,1);
continue;
}
double ang=atan2(y[i],x[i]),ex=acos((1.0*R*R+dis*dis-mid*mid)/(2*dis*R));
double l=ang-ex,r=ang+ex;
while(l<0)l+=2*Pi;while(r<0)r+=2*Pi;
int L=l/nd,R=r/nd;
q[++Q]=(ques){i,L+1,1,l-L*nd};
q[++Q]=(ques){i,R+1,-1,r-R*nd};
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);
}
}
sort(q+1,q+Q+1,cmp);int ans = 0;
while(bfs()) ans += dfs(s, Inf) ;
if(ans==n)return true;
for(int i = 1; i <= Q; i++)
if(q[i].opt == 1)
{
Add(q[i].u, q[i].v + n, 1);
if(bfs())ans+=dfs(s, Inf);
if(ans==n)return true;
}
else del(q[i].u, q[i].v + n ,ans );
return false;
}
int main()
{
n=gi();R=gi();nd=2.*Pi/n;s=0;t=n<<1|1;
for(int i=1;i<=n;i++){x[i]=gi(),y[i]=gi();}
double l=0,r=300;
while(r-l>eps)
{
double mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid;
}
printf("%.10lf
",l);
return 0;
}