Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
A safe way
Time Limit: 3000MSMemory Limit: 65536K
Total Submissions: 1971Accepted: 379Special Judge


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.

Sample Input

0 0 5 5
1 0
3 0
3 2
1 2

Sample Output



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