Asteroid Overlap Optimization

The year is 2115. The Asteroid Communication Ministry built a relay system a decade ago. However, too many small asteroids now interfere with communications and endanger maintenance aircraft. The Interplanetary Coalition to Prevent Catastrophes (ICPC) has tasked Han Duo and his team of elite pilots with destroying those asteroids. With a shortage of missiles, Han can only fire limited ammunition. Fortunately, if two asteroids overlap enough, a single missile can take them both out.

Your mission is to calculate the time t (in seconds) at which the overlapping area of the two moving asteroids is maximized. Each asteroid is represented by a non‐rotating two‐dimensional convex polygon and moves with a fixed velocity. The position of each vertex at time t is given by:

\( (x + v_x t,\; y+ v_y t) \)

where \( (x,y) \) is the initial coordinate of the vertex and \( (v_x,v_y) \) is the velocity of that asteroid.

You are to use an appropriate optimization method (such as ternary search) together with standard computational geometry (polygon intersection using the Sutherland–Hodgman algorithm, for example) to determine the time when the overlapping area of the two polygons is maximized. Print the optimal time with a precision of 6 decimal places.

Note: It is guaranteed that the two asteroids will eventually have a non‐zero intersection during their motion and that the intersection area function is unimodal in the time interval where they intersect.

inputFormat

The input consists of the description of two moving convex polygons.

The input format is as follows:

1. An integer n1 (number of vertices in the first polygon).
   1. The next n1 lines each contain two real numbers representing the coordinates of a vertex of the first polygon in order.
   2. A line with two real numbers: vx1 and vy1, the components of the velocity of the first polygon.
2. An integer n2 (number of vertices in the second polygon).
   1. The next n2 lines each contain two real numbers representing the coordinates of a vertex of the second polygon in order.
   2. A line with two real numbers: vx2 and vy2, the components of the velocity of the second polygon.

All numbers are separated by spaces or newlines.

outputFormat

Output a single real number on one line: the time (in seconds) at which the overlapping area of the two polygons is maximized. The answer must be printed with exactly 6 decimal places.

sample

4
0 0
2 0
2 2
0 2
1 1
4
4 4
6 4
6 6
4 6
-1 -1

2.000000