J. Maximum Scaling
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given two convex polygons $$$P$$$ and $$$Q$$$ on the $$$xy$$$-plane. Find the maximum real number $$$s$$$ satisfying the following condition.

Condition: Let $$$Q'$$$ be the polygon obtained by multiplying both the $$$x$$$- and $$$y$$$-coordinates of every point of $$$Q$$$ by $$$s.$$$ It is possible to translate $$$Q'$$$ so that its entire boundary and interior are contained in the boundary and interior of $$$P.$$$

Note that the only operation allowed on $$$Q'$$$ in the above condition is translation. Rotation and reflection are not allowed.

Figure J.1 (a)–(c) illustrates the three test cases in Sample Input 1. In the first test case, let $$$Q'$$$ be the polygon obtained by scaling the polygon $$$Q$$$ by $$$0.5$$$. The red polygon in Figure J.1 (d) shows the polygon obtained by further translating $$$Q'$$$ by $$$5$$$ in the $$$x$$$-direction and by $$$5$$$ in the $$$y$$$-direction. All points on the boundary and in the interior of this polygon are contained in the boundary and interior of $$$P.$$$ The maximum value of $$$s$$$ satisfying the condition is $$$0.5$$$. If $$$s$$$ is greater than $$$0.5$$$, the polygon $$$Q$$$ scaled by $$$s$$$ cannot be contained in the boundary and interior of $$$P,$$$ no matter how it is translated.

(a)(b)(c)
(d)
Figure J.1: Illustration of Sample Input 1
Input

The input contains one or more test cases, each in the following format.

$$$n$$$ $$$m$$$
$$$x_1$$$ $$$y_1$$$
$$$\vdots$$$
$$$x_n$$$ $$$y_n$$$
$$$x'_1$$$ $$$y'_1$$$
$$$\vdots$$$
$$$x'_m$$$ $$$y'_m$$$

The first line of a test case contains two integers $$$n$$$ and $$$m$$$, where $$$n$$$ is the number of vertices of the convex polygon $$$P$$$, and $$$m$$$ is the number of vertices of $$$Q$$$ ($$$3 \le n \le 500$$$, $$$3 \le m \le 500$$$). The following $$$n$$$ lines contain the coordinates of the vertices of $$$P$$$, $$$(x_1, y_1), \ldots, (x_n, y_n)$$$, in counterclockwise order. Similarly, the next $$$m$$$ lines contain the coordinates of the vertices of $$$Q$$$, $$$(x'_1, y'_1), \ldots, (x'_m, y'_m)$$$, in counterclockwise order. Each coordinate is an integer between $$$0$$$ and $$$10^4$$$, inclusive.

It is guaranteed that the polygons $$$P$$$ and $$$Q$$$ are simple, and that each interior angle is less than $$$180$$$ degrees.

The end of the input is indicated by a line containing two zeros. The number of test cases does not exceed $$$100$$$. The sum of $$$n$$$ over all the test cases does not exceed $$$500$$$. The same applies to $$$m$$$.

Output

For each test case, output the maximum value of the real number $$$s$$$ in a line. The output is considered correct if the absolute or relative error does not exceed $$$10^{-4}$$$.

Example
Input
3 3
10 10
40 10
10 40
40 40
10 40
40 10
4 3
1000 1000
6000 1000
7000 5000
2000 5000
3000 1000
3500 2000
3000 2000
4 5
2056 9041
959 2056
7944 959
9041 7944
587 7351
1400 1530
7188 504
9952 5692
5872 9923
0 0
Output
0.5
4
0.743571717879