8536: Geometry

NIO loves geometry.

One day he came out with a problem: given two convex polygons in a 2-dimension plane, each with a velocity, what is the moment when they collide? In this problem, it is considered to be a collision that two convex polygons share one point.

The first line contains an integer n (3≤n≤50000), denoting the number of vertices of the first convex polygon. Then follows n lines, each line contains two integers x_i, y_i(−10⁹≤x_i, y_i≤10⁹), denoting the ith point of the convex polygon. The points are given in counter-clockwise order.

Then follows an integer m (3≤m≤50000), and then m lines, denoting the second polygon. The format and restrictions are the same as above.

The last line contains four integers vx₁, vy₁, vx₂, vy₂(−10⁹≤vx₁, vy₁, vx₂, vy₂≤10⁹). The velocity of the first polygon is (vx₁,vy₁)and the velocity of the second polygon is (vx₂,vy₂).

Output a single real number t, indicating how many units of time they collided after the initial state. If the two convex polygons collide at the initial state, print 0. If they will never collide, print −1.

Your answer will be judged to be correct if the relative or absolute error with the jury's answer is less than or equal to 10^-6.

4
0 0
1 0
1 1
0 1
4
0 2
1 2
1 3
0 3
0 0 -2 -2

0.5