All departures from the Koltsovo airport are delayed. The chief air traffic
controller has declared that he will not let any aircraft get off the ground as
long as a suspicious thundercloud hangs over the airport territory. He has also
assured passengers that the wind is blowing the cloud away at a speed of one
meter per second and the sky over the airport will clear off soon. However, he
has said nothing about the wind direction.
One of the passengers has found on the Internet a satellite image of the
airport territory taken exactly one minute ago. The location of the cloud at
that time can be determined exactly from the image. The exact coordinates of
the airport are also easy to find. Is this information sufficient for
calculating the minimum time in which the air traffic controller may give the
green light to flight departures?
The cloud and the airport territory in the image can be approximately regarded
as non-degenerate strictly convex plane polygons. The first line contains the numbers n and
m of vertices of the polygons corresponding to the airport territory and to
the cloud, respectively (3 ≤ n, m ≤ 50 000). In each of the following
n lines you are given the coordinates of vertices of the polygon describing
the airport territory in the counterclockwise order. The following m lines
describe the cloud in the same format. All the coordinates are specified in
meters and are integers not exceeding 108 in absolute value. It is
guaranteed that in the image the cloud covers at least one interior point of
the airport territory.
Output the minimum number of seconds before there is no cloud over each point
of the airport territory. Output the answer with an absolute or relative error
not exceeding 10−6. If it is possible that the cloud covers no points of
the airport territory right now, output 0.
Problem Author: Daniil Ayzenshteyn
Problem Source: NEERC 2011, Eastern subregional contest