|Online Judge||Problem Set||Authors||Online Contests||User|
A safe way
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.
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.
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 2
Northeastern Europe 2004, Western Subregion
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator