0230. The Greatest Angle

Input file name:	angle.in
Output file name:	angle.out
Time limit:	250 ms
Memory limit:	64 megabytes

Consider two points A and B located strictly inside of some circle in Cartesian coordinate system. You task is to find a point C on the circle such that the angle ACB is maximal possible.

Input file

On first line of input file there is one integer N – number of tests (1 ≤ N ≤ 10000). I+1-th line describes I-th test case in format X₀, Y₀, R, X_A, Y_A, X_B, Y_B, where (X₀, Y₀) is center of the circle, R is radius of the circle, (X_A, Y_A) are point A coordinates, (X_B, Y_B) are point B coordinates. All numbers are integers. X₀, Y₀, R are not greater than 10000 by absolute value.

Output file

Output file must contain N lines, exactly one for each test case. For each case you must output X_C and Y_C – coordinates of point C, described in statement, with precision of six digits after decimal point. If there are many solutions, output any one of them.

Example:

angle.in	angle.out
2 0 0 2 1 1 -1 1 0 0 2 0 1 1 0	0.000000 2.000000 1.414214 1.414214

Source: Petrozavodsk Winter 2004. SPb ETU Contest, Sunday, February 01

Discuss       Submit a solution



Printable version