2013年7月12日 星期五

10750 - Beautiful Points

Beautiful Points

平面上有一些點名為 beauty points,找到一個點 A,其醜陋程度定義為 |AB|+|AC|,其中 B, C 是最鄰近 A 的 beauty point

給定一些 beauty points,找到一個具有最少醜陋程度的點(最漂亮的點,醜中找漂亮)。
特別注意:這個點不會是 beauty points。

Input

第一行會有一個整數表示測資組數,最多 10 組。

每組有一個整數 N (2 ≤ N ≤ 10000),表示平面上有多少的 beauty points
接下來會有 N 行,每行上會有兩個整數 X, Y (-10000 ≤ X, Y ≤ 10000),表示 beauty points 的座標。不會有兩個點具有相同座標,測資組間會有空白行。

Output

對於每組測資,輸出任何一個最漂亮的點(若有多組解,任何一組都可以),精準到小數點三位。測資組間空一行。


Sample Input


2

4
0 0
0 1
1 1
1 0

4
-1 -1
0 0
1 0
2 1
 
Sample Output

0.500 0.000

0.500 0.000