A safe way
Description
There is a map of a minefield. The border of the minefield is a polygon which has not got self-intersections or self-contacts. There are two points A and B outside of this minefield or on its border. You need to find the minimum length way from A to B. Obviously the way can not cross the minefield. However, it may contact edges or vertices of the bounding polygon.
Input
The input consists of several lines. The first line contains four numbers XA, YA, XB and YB – the coordinates of two given points. The second line contains integer number N, 3 ≤ N ≤ 100 – the number of vertices of the bounding polygon. Finally, each of the next N lines contains a coordinates X and Y of one polygon vertex, in the counterclockwise order. All the coordinates are integer numbers between −100000 and 100000. The numbers are separated by one or more spaces.
Output
The output consists of one line containing the length of a shortest safe way, with the accuracy 0.0001.
0 0 5 5
4
1 0
3 0
3 2
1 27.2361Source
Northeastern Europe 2004, Western Subregion