记录编号	586245	评测结果	AAAAAAAAAA
题目名称	[CH 6803]导弹防御塔	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.213 s
提交时间	2024-01-09 21:06:28	内存使用	9.46 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 60,M = 3e5+10;
const double eps = 1e-8;
//二分图多重匹配 
int n,m;
double t1,t2,V;
struct made{
    int ver,nx;
}e[M];
int hd[N],tot;
int match[M];
bool v[M];
struct node{
    int x,y;
}a[N],b[N]; 
void add(int x,int y){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],hd[x] = tot;
}
double distan(int x,int y){
    return (double)sqrt((a[x].x-b[y].x)*(a[x].x-b[y].x)+(a[x].y-b[y].y)*(a[x].y-b[y].y));
}//
bool dfs(int x){
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(v[y])continue;
        v[y] = 1;
        if(!match[y] || dfs(match[y])){
            match[y] = x;
            return 1;
        }
    }
    return 0;
}//模板 
void build(double mid){
    int cnt = 0;
    for(int i = 1;i <= n;i++){
        double t = t1;
        for(int k = 1;k <= m;k++){
            if(t > mid)break;
            cnt++;
            for(int j = 1;j <= m;j++){
                double dis = distan(i,j);
                if(dis / V + t <= mid)add(j,cnt);// 
            }
            t += t1 + t2;
        }
    }//建二分图 
}
bool check(double mid){
    tot = 0;
    memset(hd,0,sizeof(hd));
    memset(match,0,sizeof(match));
    build(mid);
    for(int i = 1;i <= m;i++){
        memset(v,0,sizeof(v));
        if(!dfs(i))return 0;//有一个目标未能摧毁
    }
    return 1;
}
int main(){
    freopen("missile_tower.in","r",stdin);
    freopen("missile_tower.out","w",stdout);
	scanf("%d%d%lf%lf%lf",&n,&m,&t1,&t2,&V);
	t1 /= 60;
	for(int i = 1;i <= m;i++)scanf("%d%d",&b[i].x,&b[i].y);
	for(int i = 1;i <= n;i++)scanf("%d%d",&a[i].x,&a[i].y);
	
	double l = t1,r = 1e6;
	while(l + eps < r){
	    double mid = (l + r) / 2;
	    if(check(mid))r = mid;
	    else l = mid; 
    }
    printf("%.6lf\n",l);
	
	return 0;
	
}