|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
You may not know that the official name of the “common” urban pigeon you see every day in a city is in fact “rock pigeon” or “rock dove”. Rock pigeon Rocky Dave is in love with Columba Livia, a young female rock pigeon who has keen interest in rock, pigeons, and all that relates to this kind of things. By sheer coincidence, one sunny autumn afternoon, we find them in the city suburbs sitting on the roof of the same building.
To show off his self-confident athletic gait, Rocky Dave decided not to fly over the roof to his object of affection, but to walk towards her instead. The roof is not a modern flat roof, it is a classical roof made of slopes. As the building consists of more smaller buildings joined together, its floor plan is a bit complex. Thus, the “straight line” in which Dave intends to move towards Columba Livia, appears straight only when observed from above. Rocky Dave might have to climb up, over the ridge, down on the other side into a roof valley and then up again, and so on.
We know the exact floor plan of the building, the angle of the slopes on the roof (all angles are the same), and also the original positions of both our hero and heroine on the roof. Given these data, compute the exact length of Rocky Dave’s journey, provided that Columba Livia does not leave her position before Rocky Dave reaches her.
If the path leaves the building boundary, it is Dave’s plan that whenever he meets a rain gutter on the roof edge, he would fly straight and in the same height in the direction towards Columba Livia, until he reaches the rain gutter on some other side of the building, where he would further continue his journey on foot.
To make the situation unambiguous, we present you with the geometric model of a roof. Let Z be a simple polygon in the x-y plane. A simple polygon is a polygon, whose boundary is a closed curve which does not touch or intersect itself. An acceptable pyramid is a pyramid whose base is an axis-parallel square in the x-y plane and its apex (top vertex) is located directly above the base center. The pyramid height is exactly one half of the length of its base side. Moreover, no part of the base of an acceptable pyramid lies outside Z. Note that an acceptable pyramid may formally have zero base side length and zero height, it then consists of a single node, which is also its apex.
A point X in or above the x-y plane is a point of the roof of Z if and only if it is an apex of an acceptable pyramid and no point directly above X is an apex of an acceptable pyramid.
The first line contains five integers. The first of them, N (4 ≤ N ≤ 400), is the number of corner points of the polygon formed in the x-y plane by the edges of the floor plan of the building. The next two are the x and y coordinates of Rocky Dave and the last two are the x and y coordinates of Columba Livia.
Each of the next N lines contains the x and y coordinates of one corner point of the polygon. The points are listed in the counter-clockwise order. Every side of the building is parallel with one of the axes.
Neither of the two pigeons is located outside of the given polygon. All input coordinates are integers with the absolute value of at most 105.
Output the length of Rocky Dave’s journey. The answer must have an absolute or relative error less than 10−7.
4 3 0 3 4 0 0 4 0 4 4 0 4
6 1 1 5 5 0 0 2 0 2 4 6 4 6 6 0 6
Figure 1: Illustration of Sample Input 1 and Sample Input 2