Bug2#2259

Bug2

3 seconds

256 megabytes

Hard

There is a variety of navigation problems around us. This is a problem about an algorithm called Bug2.

Bug algorithms solve the following navigation problem. There is a two-dimensional map containing obstacles of arbitrary shape, and start and finish points are given. There is also an agent, who initially stands at the start point $S$ , and whose task is to reach the finish point $F$ . It knows the coordinates of the finish point, and at any moment in time it can determine its own coordinates. The agent has $O (1)$ memory, so it cannot store the map of obstacles. The only way it can get information about the outer world is to detect whether it touches an obstacle. The agent is able to move around the obstacle, following its boundary. The problem is to reach the finish point when it is possible, and correctly report the fact of unreachability otherwise.

The Bug2 algorithm, which belongs to the family of Bug algorithms, works as follows:

1. Move towards $F$ until one of the following happens:

The finish point is reached. Then the algorithm stops.
An obstacle is encountered. Then go to step 2.

2. Define the current point as $H$ . Move around the boundary of the obstacle in the clockwise direction until one of the following happens:

The finish point is reached. Then the algorithm stops.
The point $H$ is reached. Then the finish point is unreachable and the algorithm stops.
A point $L$ is reached, which lies on the line $SF$ , $∣ LF ∣ < ∣ HF ∣$ |\textbf{LF}| < |\textbf{HF}| and it is possible to move towards $F$ without hitting an obstacle immediately. In this case, go to step 1.

One may prove the correctness of the algorithm: that is, that it reaches the finish point in finite time (that is, the length of the resulting path is finite) if it is possible, and reports that the finish point is unreachable in finite time otherwise.

Given a set of polygonal obstacles, and start and finish points, determine the length of the path that an agent directed by the Bug2 algorithm will traverse.

Input

The first line of the input file contains five integer numbers $n$ , $x_{S}$ x_S, $y_{S}$ y_S, $x_{F}$ x_F, $y_{F}$ y_F — the number of obstacles and the coordinates of the start and finish points.

The rest of the input file describes obstacles. Each description starts with a line containing an integer $m$ ( $m \geq 3$ m \ge 3) — the number of vertices in the obstacle. The following $m$ lines contain pairs of integer numbers $x_{i}$ x_i, $y_{i}$ y_i — the coordinates of the vertices of the obstacle, given in the clockwise direction. The obstacle does not have self-intersections or self-tangencies.

The total number of vertices in all the obstacles does not exceed $300000$ . No coordinate exceeds $1 0^{6}$ 10^6 by absolute value.

No vertex of an obstacle lies on the line $SF$ . Both start and finish points will lie strictly outside any obstacle. No two obstacles share common points. If there are two points $A$ and $B$ where obstacle boundaries intersect with the line $SF$ , either $∣ AF ∣ = ∣ BF ∣$ |\textbf{AF}| = |\textbf{BF}| or $∣∣ AF ∣ - ∣ BF ∣∣ > 1 0^{- 6}$ ||\textbf{AF}|-|\textbf{BF}|| > 10^{-6} will be true.

Output

Output the length of a path traversed by the agent directed by the described algorithm. The absolute or relative error of $1 0^{- 6}$ 10^{-6} is acceptable.

Examples

Example 1