ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1894. Non-Flying Weather

Time limit: 2.0 second
Memory limit: 64 MB
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?

Input

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

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.

Sample

inputoutput
4 4
400 400
600 400
600 600
400 600
0 0
1000 0
1000 1000
0 1000
540.0
Problem Author: Daniil Ayzenshteyn
Problem Source: NEERC 2011, Eastern subregional contest