2357: Farmer John
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：5
解决：2
题目描述
Farmer John owns a lot of cows that graze in the fields and walk around happily.
However, cow Bessie is very lazy and always takes the shortest route to the barn to get food. Farmer John wants to give Bessie some more walking exercises, so he placed some extra fences to make sure that Bessie cannot always take the shortest route and has to walk around the fences.
Given the current location of Bessie, the location of the barn with the food, and all locations of
the fences (modelled as line segments), farmer John wants you to compute the minimum distance
that Bessie has to walk. Bessie is not allowed to cross any fence on her route, but she is allowed to touch the fences.
输入
The first line of the input contains a single number: the number of test cases to follow. Each test
case has the following format:
• One line with four integers Bx , By , Fx and Fy satisfying −10, 000 ≤ Bx ,By ,F x ,Fy ≤ 10,000:
the location of Bessie and the location of the food.
• One line with one integer N satisfying 0 ≤ N ≤ 100: the number of fences.
• N lines, one for each fence, with four integers x1 , y1 , x2and y2 satisfying −10, 000 ≤
x1 ,y1 ,x2 ,y2 ≤ 10, 000 and x1!= x2 or y1!= y 2: the x- and y-coordinates of the begin and end points of this fence.
Integers on the same line are separated by single spaces. The current location of Bessie and the location of the food will not lie on a fence, and fences will not touch or overlap.
输出
For every test case in the input, the output should contain a single real number, rounded and
displayed to six digits after the decimal point, on a single line: the minimum walking distance.
样例输入 复制
3
0 0 10 0
1
-1 -100 -1 100
0 0 10 0
2
-1 -100 -1 100
5 4 5 -6
0 0 2 1
1
1 1 1 -1样例输出 复制
10.000000
12.806248
2.414214