Laser Beam Reflections

Time limit2sMemory limit128 MB

Summary

With up to five mirrors and fewer than six reflections on the shortest path, compute the length of the generator-to-target path, rounding to three decimals.

Level: Hard8 of 10
Topics: Geometry, Brute force, DFS
Solved: No attempts yet

Problem

A laser beam generator, a target object, and some mirrors are placed on a plane. The mirrors stand upright on the plane, and both faces of each mirror are flat and reflect beams. Because the beam can reach the target after different sequences of reflections, several initial directions may hit the target. Your task is to find the shortest beam path from the generator to the target and report its length.

The figure below shows examples of possible beam paths; the bold line is the shortest one.

Examples of possible paths

Input

The input consists of several datasets. A line containing a single zero marks the end of the input.

Each dataset has the following format. Every value in a dataset except $n$ is an integer between $0$ and $100$ inclusive.

$n$ $PX_1\ PY_1\ QX_1\ QY_1$ $\vdots$ $PX_n\ PY_n\ QX_n\ QY_n$ $TX\ TY$ $LX\ LY$

The first line of a dataset contains an integer $n$ ( $1 \le n \le 5$ ), the number of mirrors. The next $n$ lines describe the mirrors: $(PX_i, PY_i)$ and $(QX_i, QY_i)$ are the two endpoints of mirror $i$ . No two mirrors touch each other. The last two lines give the target position $(TX, TY)$ and the generator position $(LX, LY)$ . The target and the generator are separated from each other, and both are separated from every mirror.

The target and the generator are small enough that their sizes can be ignored, and the mirrors have negligible thickness.

You may also assume the following about every dataset:

At least one path from the generator to the target exists.
The number of reflections along the shortest path is fewer than $6$ .
The shortest path never crosses or touches the line through a mirror at any point within $0.001$ of either endpoint of that mirror.
Even if the beam could freely choose to reflect or pass through whenever it meets a mirror's line within $0.001$ of an endpoint, no resulting path would be shorter than the shortest path.
Whenever a beam shot from the generator reflects off a mirror, or passes within $0.001$ of a mirror, the angle $\theta$ between the beam and the mirror satisfies $\sin(\theta) > 0.1$ , up to (but not including) the 6th reflection point.

The first figure corresponds to the first example dataset. The figure below shows the shortest paths for the remaining example datasets.

Examples of the shortest paths

Output

For each dataset, print a single line with the length of the shortest path from the generator to the target, rounded to exactly three digits after the decimal point (for example, 90.510). Do not print any extra characters.

Examples1

Example 1

Input

2
30 10 30 75
60 30 60 95
90 0
0 100
1
20 81 90 90
10 90
90 10
2
10 0 10 58
20 20 20 58
0 70
30 0
4
8 0 8 60
16 16 16 48
16 10 28 30
16 52 28 34
24 0
24 64
5
8 0 8 60
16 16 16 48
16 10 28 30
16 52 28 34
100 0 100 50
24 0
24 64
0

Expected output