Beautiful Points

There are several points on the plane named beauty points. Given a point A, its ugliness is defined as |AB|+|AC|, where B and C are two beauty points nearest to A.

Your task is: given beauty points, find the most beautiful point, i.e., the point having least ugliness. Note: the most beautiful point doesn't have to be a beauty point.

Input

The first line of the input contains the number of the test cases, which is at most 10. The descriptions of the test cases follow. The first line of a test case descriptions contains an integer N (2 ≤ N ≤ 10000), which is the number of beauty points. Each of the next N lines contains two integers X and Y separated by a space (-10000 ≤ X, Y ≤ 10000) being the coordinates of a beauty point. No two beauty points in a test case description have the same coordinates. The test cases are separated by blank lines.

Output

For each test case in the input, output the coordinates of any most beautiful point separated by a space, with at least three digits after the decimal point. Print a blank line between test cases.

Examples

Input	Output
2 4 0 0 0 1 1 1 1 0 4 -1 -1 0 0 1 0 2 1	0.500 0.000 0.500 0.000

題目是要找到平面上一點到給定的其中最近兩點距離最小。
很簡單地會想到兩點的中點，因此找最鄰近點對的中點。

用 D&C 分治的想法去解。

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y < a.y;
    }
};
int mndist;
Pt D[10005];
double px, py;
void merge(int l, int r) {
    if(l >= r)  return;
    int i, j, m;
    m = (l+r)/2;
    merge(l, m);
    merge(m+1, r);
    for(i = m; i >= l; i--) {
        if((D[i].x-D[m].x)*(D[i].x-D[m].x) >= mndist)
            break;
        for(j = m+1; j <= r; j++) {
            if((D[i].x-D[j].x)*(D[i].x-D[j].x) >= mndist)
                break;
            int v = (D[i].x-D[j].x)*(D[i].x-D[j].x)+(D[i].y-D[j].y)*(D[i].y-D[j].y);
            if(v < mndist) {
                mndist = v;
                px = (D[i].x+D[j].x)/2.0;
                py = (D[i].y+D[j].y)/2.0;
            }
        }
    }
}
int main() {
    int testcase, n, i;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%d %d", &D[i].x, &D[i].y);
        sort(D, D+n);
        mndist = 0xfffffff;
        merge(0, n-1);
        printf("%.3lf %.3lf\n", px, py);
        if(testcase)    puts("");
    }
    return 0;
}