#P3035. 导弹防御塔

    ID: 2167 传统题 1000ms 512MiB 尝试: 243 已通过: 79 难度: 6 上传者: 标签>难度分类提高排序与序列处理二分答案图论二分图建模Kuhn 算法动态规划有限候选集缩减CF2100Poetize3

导弹防御塔

导弹防御塔

题目描述

Freda 有 nn 座导弹防御塔,用来抵御 mm 名入侵者。每座塔导弹充足,一次只能发射一枚。开始发射后,要经过 t1t_1 秒导弹才离开塔。导弹离开后,该塔要冷却 t2t_2 分钟才能开始发射下一枚导弹。各塔可以同时使用。

所有导弹的飞行速度都是 vv。从塔到目标的水平直线距离为 dd 时,导弹离开塔后还需飞行 dv\frac{d}{v} 分钟,到达时立即击毁该目标。飞行期间,发射塔可照常冷却并准备下一次发射。

给定所有坐标与发射参数,求最早能在多少分钟内击毁所有入侵者。

输入格式

第一行五个正整数 n,m,t1,t2,vn,m,t_1,t_2,v。

接下来 mm 行,每行两个整数,表示一名入侵者的坐标。最后 nn 行,每行两个整数,表示一座防御塔的坐标。

输出格式

输出一行一个实数,表示击毁所有入侵者所需的最少分钟数,四舍五入保留 66 位小数。

数据范围

1≤n,m≤501\le n,m\le50,坐标的绝对值不超过 10410^4,1≤t1,t2,v≤20001\le t_1,t_2,v\le2000。

样例

3 3 30 20 1
0 0
0 50
50 0
50 50
0 1000
1000 0
91.500000