Description

给定平面上N个点, 请找出这N个点的最近点对.

Input

第一行输入M表示包含M组测试数据，每组先输入N (N<=50000), 接着输入N个坐标(x,y), x和y均为int型整数.

Output

输出最近点对距离,精度保留2位小数

Sample Input

2
3 1 1 2 1 3 5 
10 851644 996635 20388 842736 262145 615142 890041 434439 787213 89181 99282 310353 179500 803495 728862 687090 225650 604015 765534 465397 

Sample Output

1.00
38153.57

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct position_t {
    int x;
    int y;
} pos[100001], tpos[100001], swappos[100001];
int n;

double mydistance(int i, int j) {
    return 1.0*(pos[i].x-pos[j].x)*(pos[i].x-pos[j].x) + 1.0*(pos[i].y-pos[j].y)*(pos[i].y-pos[j].y);
}

double fun() {
    double mymin = ((long long int)2)<<60;
    for(int i=0; i<n-1; i++) {
        for(int j=i+1; j<n; j++) {
            double d = mydistance(i,j);
            if(mymin > d) {
                mymin = d;
            }
        }
    }
    return sqrt(mymin);
}

int cmp_xy (const void * a, const void * b) {
    position_t *p1 = (position_t *)a;
    position_t *p2 = (position_t *)b;
    if(p1->x != p2->x) {
        return p1->x - p2->x;
    }
    else {
        return p1->y - p2->y;
    }
}

int cmp_y (const void * a, const void * b) {
    position_t *p1 = (position_t *)a;
    position_t *p2 = (position_t *)b;
    return p1->y - p2->y;
}

double divide(int low, int high) {
    if(low >= high) {
        return ((long long int)2)<<60;
    }
    if(low+1 == high) {
        return mydistance(low, high);
    }
    int mid = (low+high)/2;
    int midx = pos[mid].x;
    double d1 = divide(low, mid);
    double d2 = divide(mid+1, high);
    double mymin = d1>d2 ? d2 : d1;
    
    int k = 0;
    for(int i=low; i<=high; i++) {
        if(abs(midx-pos[i].x) < mymin) {
            tpos[k].x = pos[i].x;
            tpos[k].y = pos[i].y;
            k++;
        }
    }
    qsort(tpos, k, sizeof(position_t), cmp_y);
    for(int i=0; i<k-6; i++) {
        for(int j=1; j<=6; j++) {
            double temp = 1.0*(tpos[i].x-tpos[i+j].x)*(tpos[i].x-tpos[i+j].x) + 1.0*(tpos[i].y-tpos[i+j].y)*(tpos[i].y-tpos[i+j].y);
            if(temp < mymin) {
                mymin = temp;
            }
        }
    }
    
    return mymin;
}

int solve() {
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d%d", &pos[i].x, &pos[i].y);
    }
    
    //printf("%.2lf\n", fun());
    
    qsort(pos, n, sizeof(position_t), cmp_xy);
    printf("%.2lf\n", sqrt(divide(0, n-1)));
}

int main() {
    int m;
    scanf("%d", &m);
    for(int i=0; i<m; i++) {
        solve();
    }
}