Optimal Messenger Delivery Time

Misha needs to send packages to his friend Nadia while both are travelling along predetermined paths. They move at a constant speed of \(1\) on a 2D plane along piecewise‐linear routes. Misha will hand over the package to a messenger at some point along his route and the messenger will travel in a straight line (also at speed \(1\)) to intercept Nadia who is meanwhile following her own route. The delivery time is the time elapsed between the package pick–up and Nadia receiving it. Your task is to compute the minimum possible delivery time.

More formally, let Misha’s path be given as a sequence of points \(P_0, P_1, \dots, P_{n-1}\) and Nadia’s path as \(Q_0, Q_1, \dots, Q_{m-1}\). Since all three (Misha, Nadia, and the messenger) move at constant speed \(1\), the time taken to traverse a segment equals its Euclidean length. Given any time \(t\) (measured along Misha’s journey) the position of Misha is determined by linear interpolation along his path, and similarly for Nadia. If Misha hands over the package at time \(t\) (when he is at position \(P(t)\)) and Nadia is intercepted at time \(t+T\) (when she is at \(Q(t+T)\)), then the messenger must travel a distance equal to \(\|P(t)-Q(t+T)\|\) in time \(T\). Since his speed is \(1\), this is possible if and only if

[ |P(t) - Q(t+T)| \le T. ]

Your goal is to choose a hand–over time \(t\) and a meeting time \(t+T\) (with \(t+T\) on Nadia’s path) so that \(T\) is minimized and the above inequality holds. Note that the messenger’s travel starts when Misha hands over the package.

Input format: The first part of the input describes Misha’s path followed by Nadia’s path. For each path, the first line contains an integer indicating the number of points on that path. The following lines each contain two real numbers representing the coordinates of a point. Since the moving speed is \(1\), the time to traverse a segment equals its Euclidean length.

Output format: Output a single real number: the minimum possible delivery time. Your answer is accepted if it has an absolute or relative error of at most \(10^{-6}\).

inputFormat

The input begins with the description of Misha’s path followed by Nadia’s path.

<n>
P0.x P0.y
P1.x P1.y
... 
P(n-1).x P(n-1).y
<m>
Q0.x Q0.y
Q1.x Q1.y
... 
Q(m-1).x Q(m-1).y

Here, n (or m) is the number of points on the corresponding path. The points are given in the order they are visited.

outputFormat

Output a single line with one real number: the minimum delivery time, with at least 6 digits of precision.

sample

2
0 0
10 0
2
10 0
0 0

0.000000