0083. Triangle with the Smallest Perimeter

Имя входного файла:	smallper.in
Имя выходного файла:	smallper.out
Ограничение по времени:	500 ms
Ограничение по памяти:	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

Источник: Petrozavodsk Winter 2003. St. Petersburg Contest II, Thursday, February 06

Обсудить       Отправить решение



Версия для печати