Picture
by Cartman0052007 via Wikimedia Commons, cc by
Despite the unfortunate incident last summer, which
resulted in ten little puppies, you have been tasked with
taking care of your neighbors’ dogs again. Shadow and Lydia may
be very cute mutts, but this year you have strict instructions
to walk them one by one. However, you have other things to do
during the summer than walking dogs! Like playing fetch and
solving programming problems! It seems terribly inefficient to
walk the dogs one at a time.
Shadow and Lydia have a particular walk they each prefer and
know by heart. If you just let them out, they will follow their
favorite walk, eventually ending up in their respective
doghouses. Problem solved!
Sadly, you realize that if you just let both dogs out at the
same time and let them do their walks on their own, they might
get too close to each other. If they get too close, they will
leave their favorite walk to “have some fun’’ and you are not
sure you can find good homes for any more puppies. To ensure
this does not happen, you need to calculate the minimum
distance between the dogs when they are out walking on their
own.
Both dogs start at the same time and keep exactly the same
pace. Immediately after a dog arrives at its doghouse it stays
inside and goes to sleep, so we no longer need to worry about
the distance to the other dog, even though the other dog may
still walk for a while longer. Note that a dog is still awake
at the exact moment of entering its house and falls asleep
immediately after entering.
Input
The first line of input consists of an integer $n$ ($2
\le n \le 100\, 000$), the number of points describing
the walk of Shadow. The next $n$ lines contain $2$ integers each, giving the
$x$ and $y$ coordinates of Shadow’s walk. Two
consecutive points in the walk always differ in at least one
coordinate. All coordinates are nonnegative and at most
$10\, 000$. Similarly, the
next line contains an integer $m$ ($2
\le m \le 100\, 000$), the number of points describing
the walk of Lydia. The next $m$ lines describe its walk in the
same format as for Shadow.
Output
Output the minimum distance between the two dogs during
their walks. The numbers should be accurate to an absolute or
relative error of at most $10^{4}$.
Sample Input 1 
Sample Output 1 
2
0 0
10 0
2
30 0
15 0

10

Sample Input 2 
Sample Output 2 
5
10 0
10 8
2 8
2 0
10 0
9
0 8
4 8
4 12
0 12
0 8
4 8
4 12
0 12
0 8

1.414213562373
