Pakhom stands at the point S and wants to reach the point T to buy the land there. But he noticed a gully, which represents a polyline ABC. What is the length of the shortest path Pakhom should walk if he doesn't want to fall into the gully?
![Problem illustration](/image/get.aspx/e1336f99-f359-42a8-8a28-5be4660e0a4d)
Input
The first line contains the number of testcases n (1 ≤ n ≤ 5000). Each of the next n lines contains one testcase. Each testcase is written as 10 space-separated integers: xS, yS, xT, yT, xA, yA, xB, yB, xC, yC, the coordinates of the points S, T, A, B, and C, respectively. All points within the test case are different. Points S and T don't belong to the polyline ABC. All numbers in test cases don't exceed 10 by absolute value.
Output
For each test case output the answer on a separate line. The answer should be precise up to 10−6.
Sample
input | output |
---|
3
1 2 5 6 4 4 5 2 1 6
2 2 4 3 1 3 3 3 3 1
2 1 4 4 3 2 4 3 1 4 | 8.000000
3.650282
3.828427 |
Problem Author: Petr Lezhankin
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009