Problem J
Traveling in another dimension
Input: standard input
Output: standard output
Many of us would like to break the barrier of dimensions but the fact is that this is not that easy. Some consider Time as the fourth dimension and many others have other ideas. Some just ignore the concept of time. Our scientist friend Arnold has discovered some ways to travel in four dimensions. But the problem is that he being a three-dimensional animal has to spend more energy to go from one point to another in four-dimensional space and this energy is proportional to the square of the distance between the two points. Arnold has taken many of his friends to the four-dimensional world. The problems they face are:
a) Safety problem: The four-dimensional creatures come from nowhere and hit them. It is very difficult for them to track the four-dimensional creatures.
b) Losing way: They always lose their way in the four dimensions.
To avoid this problems they have made a tracking device and has discovered the moving paths of the four dimensional creatures and also has discovered a straight line (a four dimensional straight line is of the form Aw + Bx+ Cy+ Dz+ E=0) which is very safe. They have started building house on or beside the line. They have transformed the coordinate system along the safe line and uses a single dimensional coordinate system on the line. So if two points has coordinates d1 and d2 the distance between them is |d1-d2| and the cost to go from one point to another is proportional to the square of the distance between them. Now given the coordinates of Arnold's friends' houses you have to find out the coordinate of Arnold's house. Arnold builds his house in such a place from where his effort of visiting his friends' house will be minimum. Initially Arnold is in his home. Arnold visits a friend's house, stops there and then returns home, stops there and then go to another friend's house and so on. His final position is also in his home. Note that as they are all three-dimensional creatures so their houses are also three-dimensional. So in the same place in four dimensions there can be more than one house. Another important thing here is that Arnold stops in every house. If he had not done that he would have required more energy.
Input
The input contains several blocks. Each block contains an integer N (N>=0 && N<=10000) indicating the number of Arnold's friends in the four dimensions and then contains the N coordinates of their houses. The input is terminated by the end of file.
Output
The output contains Arnold's coordinate if when Arnold stops at each house and when his voyage is continuous (He starts from his home follows the same path as before but never stops anywhere). These two coordinates will be separated by a single space. If Arnold's coordinates cannot be determined print a –1 (minus one). (Note that if one coordinate is found the other will also be found) The outputs for each block will be in separate lines. The output format is shown in the sample output. If there are more than one such places (in the first case or in the second case) print the smallest coordinate.
Sample Input:
1 100
1 200
2 300 300
Sample Output:
(Explanation,
why Arnold needs more energy if he does not stop at each house:
Let’s
assume that Arnold is going from point A to point C
A----------------------- B -------------------- C
If he does not stop at B he will require an energy proportional to AC*AC. If he stops at B and then goes to C then he will need energy proportional to (AB*AB + BC*BC). You don’t have to be magician to prove that (AB*AB + BC*BC) < (AC*AC). Change of direction does not cost any energy. )