Description
Freda的城堡——
“Freda，城堡外发现了一些入侵者！”
“喵...刚刚探究完了城堡建设的方案数，我要歇一会儿嘛lala~”
“可是入侵者已经接近城堡了呀！”
“别担心，rainbow，你看呢，这是我刚设计的导弹防御系统的说~”
“喂...别卖萌啊……”
Freda控制着N座可以发射导弹的防御塔。每座塔都有足够数量的导弹，但是每座塔每次只能发射一枚。在发射导弹时，导弹需要T1秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要T2分钟来冷却。
所有导弹都有相同的匀速飞行速度V，并且会沿着距离最短的路径去打击目标。计算防御塔到目标的距离Distance时，你只需要计算水平距离，而忽略导弹飞行的高度。导弹在空中飞行的时间就是 (Distance/V) 分钟，导弹到达目标后可以立即将它击毁。
现在，给出N座导弹防御塔的坐标，M个入侵者的坐标，T1、T2和V，你需要求出至少要多少分钟才能击退所有的入侵者。
Input
第一行五个正整数N,M,T1,T2,V。
接下来M行每行两个整数，代表入侵者的坐标。
接下来N行每行两个整数，代表防御塔的坐标。
Output
输出一个实数，表示最少需要多少分钟才能击中所有的入侵者，四舍五入保留六位小数。
二分答案，网络流判定
#include<cstdio>
#include<cmath>
const int N=;
int n,m,S,T;
int mx[],my[],nx[],ny[];
int es[N],enx[N],e0[N],ep,h[N],q[N],ev[N];
double t1,t2,v;
bool bfs(){
for(int i=;i<=T;i++)h[i]=;
int ql=,qr=;
h[q[qr++]=S]=;
while(ql!=qr){
int w=q[ql++];
for(int i=e0[w];i;i=enx[i])if(ev[i]){
int u=es[i];
if(!h[u])h[q[qr++]=u]=h[w]+;
}
}
return h[T];
}
int dfs(int w,int f){
if(w==T)return f;
int c,used=;
for(int i=e0[w];i;i=enx[i])if(ev[i]){
int u=es[i];
if(h[u]!=h[w]+)continue;
c=f-used;
if(c>ev[i])c=ev[i];
c=dfs(u,c);
ev[i]-=c;
ev[i^]+=c;
used+=c;
if(f==used)return f;
}
h[w]=;
return used;
}
inline void adde(int a,int b){
es[ep]=b;enx[ep]=e0[a];ev[ep]=;e0[a]=ep++;
es[ep]=a;enx[ep]=e0[b];ev[ep]=;e0[b]=ep++;
}
bool chk(double t){
ep=;
S=n*m+m+;T=S+;
for(int i=;i<=T;i++)e0[i]=;
for(int i=;i<=n;i++){
for(int k=;k<m;k++){
adde(S,(i-)*m+k+);
}
}
for(int i=;i<=m;i++)adde(n*m+i,T);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
double x=mx[j]-nx[i],y=my[j]-ny[i];
double tm=sqrt(x*x+y*y)/v;
if(tm>t)continue;
for(int k=;k<m;k++)if(tm+t1+(t1+t2)*k<=t){
adde((i-)*m+k+,n*m+j);
}
}
}
int ans=;
while(bfs())ans+=dfs(S,0x3f3f3f3f);
return ans==m;
}
int main(){
scanf("%d%d%lf%lf%lf",&n,&m,&t1,&t2,&v);
for(int i=;i<=m;i++)scanf("%d%d",mx+i,my+i);
for(int i=;i<=n;i++)scanf("%d%d",nx+i,ny+i);
t1/=.;
double L=,R=1e5;
for(int i=;i<;i++){
double M=(L+R)*.;
if(chk(M))R=M;
else L=M;
}
printf("%.6f\n",L);
return ;
}