A :: Ardenia
Time Limit: 3 Seconds Memory Limit: 131072 KB
Welcome to Ardenia. Ardenia is a mythical land, filled with adventure and danger, dwarves and dragons, mages and rouges. And puzzles. Lots of puzzles. Actually, the love for puzzles is the most important life ingredient of the inhabitants, and the only part they have in common.
This month, the people of Ardenia wonder what is the distance between two line segments in three dimensional space. (The distance between segments is defined as the minimum among distances between two points of different segments.) Actually, this problem had originally some motivation, but as nobody from Ardenia cares about motivations, neither should you.
Input
The input contains several test cases. The first line of the input contains a positive integer Z <= 105 , denoting the number of test cases. Then Z test cases follow, each conforming to the format described below.
The first line of the input instance contains six space-separated integers x1, y1, z1, x2, y2, z2 є [- 20, 20]. Points (x1, y1, z1) and (x2, y2, z2) are the (different) endpoints of the first segment. The second line contains six integers in the same format, describing the second segment.
Output
For each test case, your program has to write an output conforming to the format described below.
You should output a single line consisting of two co-prime integers l and m > 0, such that l /m is the square distance between the given two segments.
Sample Input
2 0 0 0 1 1 1 1 1 1 2 2 2 1 0 0 0 1 0 1 1 0 2 2 0
Sample Output
0 1 1 2Submit
Source: Central European Regional Contest 2010