杭电1007-----C语言实现

这道题花了好久的时间才做出来，刚开始没有思路，最后看了网上的解答，好难得样子，每次都没有看完，但是掌握了大概思想，今天试着做了一下，已ac

主要思想：先将点对按照x排序，再在x排好序的基础上按照y来排序，这个用qsort函数就可直接完成，然后主要就是分治法的运用，将点分成小份来寻找最近点对。每次有三种情况，即你分成的两堆点，最近点对的两点都在1.左边那堆  .右边那堆  .左边右边各一个，, 2两种情况很好想，主要是第三种情况，关于第三种情况，网上有很多分析有详细说明最少只需要比较6个点即可，我的代码为了方便，我比较了7个点。

下面是我的代码：

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

#define ref 1e20;

#define min(a,b) a>b?b:a;

typedef struct point {

    double x, y;

}Point;

Point p[];

int cmpx_y(const void *a, const void *b) {

    double x1, y1, x2, y2;

    x1 = (*(Point *)a).x;

    y1 = (*(Point *)a).y;

    x2 = (*(Point *)b).x;

    y2 = (*(Point *)b).y;

    if (x1 != x2)

        return x1 > x2 ? - : ;

    return y1 > y2 ? - : ;

}

double length_(Point p1, Point p2) {

    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));

}

double devide(int low, int high) {

    double min_ = ref;

    if (low == high)

        return ref;

    if (low +  == high) {

        return length_(p[low], p[high]);

    }

    int mid = (low + high) / ;

    double d;

    int i, j;

    if (high - low < ) {//总共都不足七个点时就直接算出来

        d = ref;

        for (i = low; i < high; i++) {

            for (j = i + ; j < high; j++) {

                d = min(d, length_(p[i], p[j]));

            }

        }

        return d;

    }

    double d1 = devide(low, mid);

    double d2 = devide(mid + , high);

    min_ = min(d1, d2);

    for (i = mid - ; i <= mid + ; i++) {

        for (j = i + ; j <= mid + ; j++) {

            d = min(min_, length_(p[i], p[j]));

        }

    }

    return d;

}

int main() {

    int n;

    int i, j, k;

    while (scanf("%d", &n) != EOF&&n != ) {

        for (i = ; i < n; i++) {

            scanf("%lf%lf", &p[i].x, &p[i].y);

        }

        qsort(p, n, sizeof(p[]), cmpx_y);

        double d = devide(, n - );

        printf("%.2lf\n", d / );

    }

}