Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2019
Screamers in the Storm
screamers.c, screamers.cpp, Screamers.java, screamers.py
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.
Input Specification
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 Specification
Output the length of Rocky Dave's journey. The answer must have an absolute or relative error
less than 10-7.
Output for Sample Input 1
Sample Input 1
4.828427124746
4
3034
0
0
4
0
4
4
0
4
Sample Input 2
Output for Sample Input 2
6
1155
6.292528739884
0
0
2
0
2
4
6
4
6
6
0
6
e
e
s
s
Figure 1: Illustration of Sample Input 1 and Sample Input 2
