1 人解决，2 人已尝试。
1 份提交通过，共有 77 份提交。
9.9 EMB 奖励。
单点时限: 10.0 sec
内存限制: 256 MB
Mary Ice is a member of a spy group. She is about to carry out a secret operation with her colleague.
She has got into a target place just now, but unfortunately the colleague has not reached there yet. She needs to hide from her enemy George Water until the colleague comes. Mary may want to make herself appear in George’s sight as short as possible, so she will give less chance for George to find her.
You are requested to write a program that calculates the time Mary is in George’s sight before her colleague arrives, given the information about moves of Mary and George as well as obstacles blocking their sight.
Read the Input section for the details of the situation.
The input has the following format:
$Time \ R \
L \
MaryX_{1} \ MaryY_{1} \ MaryT_{1} \
MaryX_{2} \ MaryY_{2} \ MaryT_{2} \
\vdots \
MaryX_{L} \ MaryY_{L} \ MaryT_{L} \
M \
GeorgeX_{1} \ GeorgeY_{1} \ GeorgeT_{1} \
GeorgeX_{2} \ GeorgeY_{2} \ GeorgeT_{2} \
\vdots \
GeorgeX_{M} \ GeorgeY_{M} \ GeorgeT_{M} \
N \
BlockSX_{1} \ BlockSY_{1} \ BlockTX_{1} \ BlockTY_{1} \
BlockSX_{2} \ BlockSY_{2} \ BlockTX_{2} \ BlockTY_{2} \
\vdots \
BlockSX_{N} \ BlockSY_{N} \ BlockTX_{N} \ BlockTY_{N}
$
The first line contains two integers. $Time$ ($0 \le Time \le 100$) is the time Mary’s colleague reaches the place. $R$ ($0 < R < 30000$) is the distance George can see – he has a sight of this distance and of 45 degrees left and right from the direction he is moving. In other words, Mary is found by him if and only if she is within this distance from him and in the direction different by not greater than 45 degrees from his moving direction and there is no obstacles between them.
The description of Mary’s move follows. Mary moves from ($MaryX_{i}$, $MaryY_{i}$) to ($MaryX_{i+1}$, $MaryY_{i+1}$) straight and at a constant speed during the time between $MaryT_{i}$ and $MaryT_{i+1}$, for each $1 \le i \le L - 1$.
The following constraints apply: $2 \le L \le 20$, $MaryT_1 = 0$ and $MaryT_L = Time$, and $MaryT_{i}$ < $MaryT_{i+1}$ for any $1 \le i \le L - 1$. The description of George’s move is given in the same way with the same constraints, following Mary’s. In addition, $(GeorgeX_j, GeorgeY_j)$ and $(GeorgeX_{j+1}, GeorgeY_{j+1})$ do not coincide for any $1 \le j \le M - 1$. In other words, George is always moving in some direction.
Finally, there comes the information of the obstacles. Each obstacle has a rectangular shape occupying $(BlockSX_k, BlockSY_k)$ to $(BlockTX_k, BlockTY_k)$. No obstacle touches or crosses with another. The number of obstacles ranges from $0$ to $20$ inclusive.
All the coordinates are integers not greater than $10000$ in their absolute values. You may assume that, if the coordinates of Mary’s and George’s moves would be changed within the distance of $10^{-6}$, the solution would be changed by not greater than $10^{-6}$.
Print the calculated time in a line. The time may be printed with any number of digits after the decimal point, but should be accurate to $10^{-4}$.
50 100 2 50 50 0 51 51 50 2 0 0 0 1 1 50 0
50