0083. Triangle with the Smallest Perimeter

Input file name:	smallper.in
Output file name:	smallper.out
Time limit:	500 ms
Memory limit:	16 megabytes

You are given the angle on the plane with the vertex in point C The point M lying inside this angle.

Find the two points A and B lying on different sides of the angle such that M ∈AB and perimeter of triangle ABC is the smallest possible.

Input file

The first line of input contains the number of test cases N (1 ≤ N ≤ 10000). Each test consists of integer numbers (X_C,Y_C) – coordinates of the vertex of the angle, (x_a,y_a) and (x_b,y_b) – angle sides directing vectors and (X_M,Y_M) – coordinates of the point M.

Output file

For each test case print the smallest possible perimeter of the triangle ABC with at least four digits after the decimal point.

Separate output for different test cases with a single blank line.

Examples:

smallper.in	smallper.out
1 0 0 0 1 1 0 2 4	20

Source: Petrozavodsk Winter 2003. St. Petersburg Contest II, Thursday, February 06

Discuss       Submit a solution



Printable version