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

NEERC 2011, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. 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?


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.


4 4
400 400
600 400
600 600
400 600
0 0
1000 0
1000 1000
0 1000
Problem Author: Daniil Ayzenshteyn
Problem Source: NEERC 2011, Eastern subregional contest
To submit the solution for this problem go to the Problem set: 1894. Non-Flying Weather