eolymp
bolt
Try our new interface for solving problems
Problems

Formula 42

Formula 42

A new racing track is being constructed for Flatland Grand Prix Formula 42 race. Well known track architect Herman Kilkin was invited, and he has prepared the track plan. However, when the construction began it turned out that there is a problem with the project.

Formula 42 racing track is an area delimited by two borders. Each border is a closed polyline that is a boundary of a convex polygon. The inner border is completely inside the outer border and has no common points with it. The racing car in Formula 42 is a circle. There are no limits for its radius, so the larger is the circle, the more spectacular the race is.

The problem with the track project is that Herman has only designed the outer border and the inner border separately. Their relative position is not specified. Now the company that is constructing the track can choose any relative position of the borders. They want to place them in such way that the race was most spectacular. However, they can only make parallel translations of the borders, but cannot rotate, flip or modify them in any other way.

It is required to find such relative position of the borders, that the resulting track can be used for the race with the maximal possible size of the racing car. The track can be used by a racing car of radius r, if the car of such radius can drive a complete lap around the inner border while staying at track. It is allowed to touch the borders. Formally, for a point P inside the inner border there must be such continuous closed polyline, such that P is inside this polyline, and for any point on the polyline a circle of radius r with its centre in this point is inside the outer border and outside of the inner border, touching is allowed.

Help the construction company to deal with Herman’s plan, and find out for what maximal radius of the racing car they can construct a racing track with the given design of its inner and outer borders.

Input

Input contains descriptions of two convex polygons, their boundaries give the shape of the outer and the inner borders, respectively.

The first line contains n (3n100) - the number of vertices of the first polygon. The following n lines contain two integers xi and yi (0xi, yi1000) each -coordinates of the vertices of the first polygon.

The next line contains an integer m (3m100) - the number of vertices of the second polygon. The following m lines contain two integers xi' and yi' each—coordinates of the vertices of the second polygon.

Vertices of each polygon are given in counter clockwise order. Polygons are convex, no three points of one polygon are on the same line. It is guaranteed that the polygons can be translated in such way that the second one is completely inside the first one, and their boundaries have no common points.

Output

Output one real number - the maximal possible radius of the racing car. The answer must be correct with absolute or relative error not exceeding 10-6.

prb8719.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
4
0 0
3 0
3 3
0 3
4
0 0
1 0
1 1
0 1
Output example #1
0.500000000
Input example #2
4
0 0
3 0
3 3
0 3
3
0 0
2 1
1 2
Output example #2
0.250000000
Source 2018, XXVI Командный чемпионат школьников Санкт-Петербурга по программированию, 18 октября, Задача K