G - Moving Points
Editorial
/ 
You are given N points in the xy-plane. Each point is in a state of linear uniform motion.
Your task is to calculate the distance to the furthest point in Manhattan distance from the origin at time t.
The first line of the input file contains the integers N and M (1 \leq N, M \leq 10^5), separated by a space.
The next N lines describe the points. Each contains four real numbers x, y, vx and vy (|x|,|y|,|vx|,|vy| \leq 10^6). This shows the initial coordinates (x, y) and velocity (vx, vy).
The next M lines describe the queries. Each line contains one real number t (0 \leq t \leq 10^6).
For each query, output the maximal Manhattan distance in one line.
The value which is accurate to within a relative or absolute value of 1E-9 will be accepted.
/ 
Time Limit: 1.5 sec / Memory Limit: 93 MB
Description
Your task is to calculate the distance to the furthest point in Manhattan distance from the origin at time t.
Input
The next N lines describe the points. Each contains four real numbers x, y, vx and vy (|x|,|y|,|vx|,|vy| \leq 10^6). This shows the initial coordinates (x, y) and velocity (vx, vy).
The next M lines describe the queries. Each line contains one real number t (0 \leq t \leq 10^6).
Output
The value which is accurate to within a relative or absolute value of 1E-9 will be accepted.
Sample Input
2 2 0 0 1 0 1 0 -1 0 0 1
Sample Output
1.0000000000 1.0000000000
Sample Input
3 3 0 0 1 1 0 1 1 0 3 3 -2 -1 0 1 2
Sample Output
6.0000000000 3.0000000000 4.0000000000
Sample Input
3 3 1 1 0.5 0 0 2 1.5 -1 1.5 0 0 1 0 1 2
Sample Output
2.0000000000 2.5000000000 3.5000000000