Background

This problem is translated from CERC 2019 “ Screamers in the Storm ”.

Problem Description

You may not know this, but the official name of the “ordinary” city pigeons you see every day is actually “rock pigeons”. The rock pigeon Rocky Dave fell in love with Columba Livia, a young female rock pigeon who has a strong interest in rocks, pigeons, and related things. On a sunny autumn afternoon, we happened to find them appearing at the same time on the roof of the same building in the suburbs of the city.

To show off his confident and agile walk, Rocky Dave decided not to fly directly to his beloved, but to walk there instead. This roof is not a modern flat roof, but a classic style made of slopes. Since the building is connected from multiple smaller parts, its layout in the plane is somewhat complex. Therefore, Dave plans to walk along a “straight line” toward Columba Livia, which is straight only when viewed from above. Rocky Dave may need to climb a ridge, cross the top, go down to the gutter on the other side, then go up again, and so on.

We have the exact floor plan of the building, the slope angle of the roof (all angles are the same), and the initial positions of the two pigeons on the roof. Based on these data, compute the exact length of Rocky Dave’s journey (assuming Columba Livia will not leave her position before Rocky Dave arrives).

If the path goes outside the boundary of the building, then according to Dave’s plan, whenever he reaches the roof-edge gutter, he will fly in a straight line at the same height toward Columba Livia until he reaches the gutter on the other side of the building, and then continue walking.

To make the situation precise, the following geometric model of the roof is given. Let $Z$ be a simple polygon in the $x$-$y$ plane (a simple polygon means a polygon whose boundary is a non-self-intersecting closed curve). An acceptable pyramid is a pyramid whose base is an axis-aligned square in the $x$-$y$ plane, whose apex is directly above the center of the base, whose height is exactly half of the side length of the base, and no part of the base may extend outside $Z$. Note that the side length and height of an acceptable pyramid may be zero, in which case it contains only a single point (the apex).

A point $X$ (in or above the $x$-$y$ plane) is considered part of the roof of $Z$ if and only if $X$ is the apex of an acceptable pyramid, and there is no point directly above $X$ that is also the apex of another acceptable pyramid.

Input Format

The first line contains five integers. The first integer $N\ (4\le N\le 400)$ is the number of vertices of the polygon in the $x$-$y$ plane that forms the outline of the building’s floor plan. The next two integers are Rocky Dave’s $x$ and $y$ coordinates, and the last two are Columba Livia’s $x$ and $y$ coordinates.

The next $N$ lines each contain the $x$ and $y$ coordinates of one vertex of the polygon. All points are given in counterclockwise order. Every edge of the building is parallel to the coordinate axes.

Neither pigeon is outside the given polygon. All input coordinates are integers with absolute value at most $10^5$.

Output Format

Output the length of Rocky Dave’s journey. The absolute or relative error of the answer must be less than $10^{-7}$.

4 3 0 3 4
0 0
4 0
4 4
0 4

4.828427124746

6 1 1 5 5
0 0
2 0
2 4
6 4
6 6
0 6

6.292528739884

Hint

Sample Explanation

Translated by DeepSeek.

Translated by ChatGPT 5