P10936 Missile Defense Towers

Freda's castle is attacked by $M$ invaders. Freda controls $N$ missile defense towers. Each tower has enough missiles, but it can fire only one missile at a time. When firing a missile, it takes $T_1$ seconds for the missile to be launched from the tower. After firing, the tower that launched the missile needs $T_2$ minutes to cool down. All missiles fly at the same constant speed $V$, and they will travel along the shortest path to hit the target. When computing the distance $Distance$ from a defense tower to a target, you only need to consider the horizontal distance and ignore the missile's flying height. The missile's flying time in the air is $Distance/V$ minutes. After the missile arrives at the target, it can destroy it immediately. Now you are given the coordinates of the $N$ missile defense towers, the coordinates of the $M$ invaders, and $T_1, T_2$, and $V$. Since Freda's friend Rainbow is about to visit the castle, you need to find the minimum number of minutes required to repel all invaders.

The first line contains five positive integers $N, M, T_1, T_2, V$. The next $M$ lines each contain two integers, representing the coordinates of an invader. The next $N$ lines each contain two integers, representing the coordinates of a defense tower.

Output a real number, meaning the minimum number of minutes needed to hit all invaders, rounded to six decimal places. An answer is considered correct if its difference from the standard answer does not exceed $10^{-5}$.

Constraints: $1 \le N, M \le 50$, the absolute value of each coordinate does not exceed $10000$, and $T_1, T_2, V$ are positive integers not exceeding $2000$. Translated by ChatGPT 5