我们考虑跑 网络流 首先是 二分图最大匹配 == 入侵者数量时 时间可以缩小
点才最多50个 50 * 50 最多发 3000 不到的导弹
3000 和 原点连 3000个边
3000 和 入侵者连 最多15000边
开 前向星 按 40000 * 8 边 差不多了就 因为连的太多了
暴力点建图 将塔分成很多导弹
每个点 最多建立50个 我们预先建出来 原点到炮塔发出得导弹上
之后 按炮弹发射和冷却路上总时间 和 入侵者相连
最后 入侵者与汇点相连
我们跑最大流 如果 最大流不是 入侵者数目 r = mid 不然 l = mid
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 40000;
int n, m;
double t1, t2, v;
int s, t;
int head[10000], depth[10000], cur[10000], cnt;
int nxt[maxn << 3], to[maxn << 3], cap[maxn << 3];
void ade(int a, int b, int c) {
to[cnt] = b;
cap[cnt] = c;
nxt[cnt] = head[a];
head[a] = cnt ++;
}
bool bfs(){
queue<int> que;
que.push(s);
memset(depth, 0, sizeof(depth));
depth[s] = 1;
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = head[u]; i != -1; i = nxt[i]) {
if(cap[i] > 0 && depth[to[i]] == 0) {
depth[to[i]] = depth[u] + 1;
que.push(to[i]);
}
}
}
if(depth[t]) return 1;
else return 0;
}
int dfs(int u, int dist) {
if(u == t) return dist;
for(int &i = cur[u]; i != -1; i = nxt[i]) {
if(depth[to[i]] == depth[u] + 1 && cap[i] > 0) {
int tmp = dfs(to[i], min(dist, cap[i]));
if(tmp > 0) {
cap[i] -= tmp;
cap[i ^ 1] += tmp;
return tmp;
}
}
}
return 0;
}
struct node{
int x, y;
}army[55], tower[55];
int dinic() {
int res = 0, d;
while(bfs()) {
for(int i = 0; i < 10000; i ++) cur[i] = head[i];
while(d = dfs(s, INF)) res += d;
}
return res;
}
double getdis(node a, node b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void init(double time){
memset(head, -1, sizeof(head));
cnt = 0;
for(int i = 1; i <= n; i ++) for(int j = 0; j <= m; j ++)
ade(s, i + j * 55, 1), ade(i + j * 55, s, 0);
for(int i = 1; i <= n; i ++) {
double sec;
for(int j = 0; j < m; j ++) {
sec = (1.0 * t1 + 1.0 * j * (t1 + t2));
for(int k = 1; k <= m; k ++) {
if(sec + getdis(army[k], tower[i]) / v < time)
ade(i + j * 55, 4000 + k, 1), ade(4000 + k, i + j * 55, 0);
}
}
}
for(int i = 1; i <= m; i ++)
ade(4000 + i, t, 1), ade(t, 4000 + i, 0);
}
int main(){
cin >> n >> m >> t1 >> t2 >> v;
t1 /= 60;
s = 0, t = 9000;
for(int i = 1; i <= m; i ++) cin >> army[i].x >> army[i].y;
for(int i = 1; i <= n; i ++) cin >> tower[i].x >> tower[i].y;
double l = 0, r = 200000;
while((r - l) > 1e-7) {
double mid = (l + r) / 2;
init(mid);
if(dinic() == m) r = mid;
else l = mid;
}
printf("%.6lf\n", r);
return 0;
}