#P2966. A safe way

    ID: 1976 远端评测题 3000ms 64MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>Northeastern Europe 2004, Western Subregion

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 2
7.2361

Source

Northeastern Europe 2004, Western Subregion