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 2013, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Podracing

Time limit: 1.0 second
Memory limit: 64 MB
Padme: These junk dealers must have a weakness of some kind.
Shmi: Gambling. Everything here revolves around betting on those awful races.
Qui-Gon: Podracing. Greed can be a powerful ally.
The ship of queen Amidala was hit in a battle and had to land on a hot planet called Tatooine. Qui-Gon Jinn went to a city to get some spare parts and fix the ship. But in order to buy the details, one needs the local currency and the Jedi didn’t have it.
The Jedi entered the shop of spare parts and met a 9-year-old boy Anakin Skywalker. From the day he was born, he’d been living on this planet together with his mother Shmi Skywalker. Anakin long wanted to take part in dangerous podracing, and he even assembled a podracer. Qui-Gon decided that he would help the boy to take part in the competitions. He also agreed with the slave owner Watto that if Anakin wins, the Jedi get spare parts, and the boy gets freedom. All you need to do is to determine the chances that Anakin wins.
The race track goes along the Oy axis and is bounded by two polylines on the left and on the right. The podracers are horizontal segments. They can move in any direction and even touch the road border, but they should always stay horizontal and be between the polylines.
The track is quite difficult as it has spots with cameras, and one is not allowed to hit them whatever happens. The cameras are material points and can be located on the track as well as outside it. If a podracer touches a camera with one of its ends, it goes unnoticed for the podracer and for the camera. Any other contact is not allowed.
The beginning of the track corresponds to the minimum y-coordinate of the vertices of the polylines, the finish line is at the maximum y-coordinate. Initially the podracer can be placed anywhere at the start level. A podracer finishes the race if it reaches the finish line. Help Qui-Gon to determine the maximum possible width of the podracer that is able to successfully finish.


The first line contains integer n — the number of vertices in the left polyline. The i-th of the next n lines contains pairs of integers xi and yi — the coordinates of i-th vertex. Then follows number m and m more lines with the coordinates of the right polyline. Then goes integer q and q lines with the coordinates of the cameras (2 ≤ n, m ≤ 105, 0 ≤ q ≤ 105). All the coordinates are integers, their absolute value is at most 109. The coordinates of vertices in each polyline are given in the increasing order of y-coordinate, the coordinates of the cameras are given in the non-decreasing order of y-coordinate. It is guaranteed that the polylines do not intersect or touch. You may assume that the minimal y-coordinates of both polylines coincide as well as the maximal ones.


Print the answer with the absolute or relative error 10−6.


0 0
5 10
5 0
10 5
10 10
6 5
Problem Author: Denis Dublennykh (prepared by Egor Shchelkonogov)
To submit the solution for this problem go to the Problem set: 1990. Podracing