# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Limits
1s, 512 MB

In order to compare race tracks, we wish to compute their lengths. A racetrack is strictly two-dimensional (no elevation). It is described by two simple polygons, where one is completely contained inside the other. The track is the region between these two polygons. We define the length of the track as the absolute minimum distance that one needs to travel in order to complete a lap. This could involve traveling on the very edge of the track and arbitrarily sharp cornering.

This is the illustration of sample input number 3 together with the shortest route around the track (dashed).

The input consists of:

one line with one integer

**n**(3 ≤ n ≤ 50), the number of vertices of the inner polygon;n lines, the i-th of which contains two integers

**x**and_{i}**y**(-5000 ≤ x_{i}_{i}, y_{i}≤ 5000): the coordinates of the i-th vertex of the inner polygon;one line with one integer

**m**(3 ≤ m ≤ 50), the number of vertices of the outer polygon;m lines, the i-th of which contains two integers

**x**and_{i}**y**(-5000 ≤ x_{i}_{i}, y_{i}≤ 5000): the coordinates of the i-th vertex of the outer polygon.

For both polygons, the vertices are given in counterclockwise order. The borders of the two polygons do not intersect or touch each other.

Output one line with one floating point number: the length of the race track. Your answer should have an absolute or relative error of at most10^{-6}.

Input | Output |
---|---|

3 1 1 2 1 1 2 3 0 0 4 0 0 4 | 3.41421356237309 |

Input | Output |
---|---|

5 1 1 5 1 5 5 3 3 1 5 4 0 0 6 0 6 6 0 6 | 16 |

Input | Output |
---|---|

5 1 1 5 1 5 5 3 3 1 5 5 0 0 6 0 6 6 3 4 0 6 | 16.4721359549996 |

This NWERC 2014 problem is licensed under the CC BY-SA 3.0 license.

You can find the original problem on the NWERC website.

0% Solution Ratio

Login to submit