Mission Impossible
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 414 Accepted Submission(s): 178
Problem Description
There are A, B, C, D four kinds of resources, A can be obtained at any point in the X-axis. B can be obtained at any point in the Y-axis. C and D each will only be able to achieve at a certain point. Giving the coordinates of C and D, the coordinates of your current location. Find the shortest path to obtain the four kinds of resources and go back.
Input
The first line contains the number T of test cases(T<=150). Each of the following T lines consists of six integers cx, cy, dx, dy, hx and hy. (cx, cy) is the coordinates of resource C, (dx, dy) is the coordinates of resource D, (hx, hy) is the coordinates of your current location. All the numbers of the input are in the range [-1000, 1000].
Output
Your program should produce a single line for each test case containing the length of the shortest path. The answers should be rounded to two digits after the decimal point.
Sample Input
3
1 1 2 2 3 3
1 1 -1 -1 -1 -1
1 -1 1 1 -1 1
Sample Output
8.49
5.66
6.83
Author
hanshuai
题意:给你C,D两点的坐标,再给起点H的坐标,A在x轴上任意位置,B在y轴上任意位置,要求从起点出发经过A,B,C,D四点后回到起点的最小距离。
有点麻烦的一道题,也是照着别人博客写的,每种情况都要分析。
用到了镜面定理:
当坐标在轴同一侧时,对其中一个点的该坐标取反,得到的新点求距离就是镜面反射的距离。
如果在不同侧,就直接求距离
附上代码:
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 struct Point 8 { 9 double x,y; 10 }h,p[3]; 11 12 double mins(double a,double b) 13 { 14 return a