Shy Polygon Placement
Time limit2sMemory limit128 MB
Given two polygons that can only slide horizontally, find the minimum bounding strip width so that every pair of points from the two polygons stays at least L apart.
- Level
Hard8 of 10
- Topics
- Geometry, Binary search, Math
- Solved
- No attempts yet
Problem
There are two polygons on a two-dimensional plane. You may translate one of the two polygons by any amount parallel to the x-axis. Its y-coordinates cannot change.
After the translation, the two polygons must be far enough apart. If one point is chosen from each polygon, the distance between the two chosen points must always be at least L.
Among all placements that satisfy this condition, minimize the difference between the maximum and minimum x-coordinates among all points belonging to the two polygons. This difference is the width of the narrowest vertical strip that covers both polygons.
Given L and the vertices of the two polygons, compute the minimum possible width.
Input
The first line contains a real number L (0.1 <= L <= 50.0).
The second line contains N1, the number of vertices of the first polygon. Each of the next N1 lines contains the x- and y-coordinates of one vertex of the first polygon, in counterclockwise order.
The next line contains N2, the number of vertices of the second polygon. Each of the next N2 lines contains the x- and y-coordinates of one vertex of the second polygon in the same format.
Each polygon has between 2 and 15 vertices, inclusive. A polygon with 2 vertices is treated as a line segment. All coordinates are integers between 0 and 500, inclusive. Each polygon is simple: except for adjacent sides sharing an endpoint, its sides do not cross or touch.
Output
Print the minimum possible difference between the maximum and minimum x-coordinates among all points belonging to the two polygons after placing them as tightly as possible while satisfying the distance condition.
Round the value to the nearest hundredth and always print exactly two digits after the decimal point.