1011 最近点对

喜欢ヅ旅行 2022-09-11 15:20 244阅读 0赞

**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();
        }
    }