32562번 - Cross Country 스페셜 저지다국어

문제

Cross-country running is a sport in which contestants run a race on an open-air course over natural terrain. To record contestants' progress, the organisers set up RFID checkpoints that each span a line across part of the course.

A contestant has finished the race once they go through all of the checkpoints in order from 1ドル$ to $n$. Crossing a checkpoint out of order conveys no advantage or penalty to a runner, as they simply have to cross it again later at the right time. Thus, for example, a runner may choose to cross a checkpoint once and then immediately cross it again in another direction if it leads to a quicker finish.

Figure C.1: Optimal running route for the course given in sample input 3.

Your objective is to find the shortest distance one has to run to finish the race, so that we can use this as the official distance of the course.

입력

• One line containing the number of checkpoints, $n$ (1ドル \le n \le 16$).
• One line containing the start coordinate of the race, $x_s$ and $y_s$ ($-10^6 \le x, y \le 10^6$).
• $n$ further lines, the $i$th of which contains the two integer coordinate of the $i$th checkpoint's endpoints, ${x_a}_i y_a x_b y_b$ ($-10^6 \le x,y \le 10^6$).
• One line containing the end coordinate of the race, $x_t$ and $y_t$ ($-10^6 \le x, y \le 10^6$).

All of the checkpoints have non-zero length; however, they may overlap either with each other or with the start and finish points.

출력

Output the shortest distance you can run to go visit all of the checkpoints in the right order, regardless of whether you touch some of the checkpoints multiple times or in the wrong order along the way.

The output must be accurate to an absolute or relative error of at most 10ドル^{-6}$.

제한

힌트