#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//定义一个点的结构体
typedef struct point {
    double x; //x坐标
    double y; //y坐标
} point;
//定义一个点对的结构体
typedef struct pair {
    point p1; //第一个点
    point p2; //第二个点
    double dist; //两点之间的距离
} pair;
//计算两点之间的距离
double distance(point p1, point p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
//比较两个点对的距离，返回较小者
pair min(pair a, pair b) {
    if (a.dist < b.dist) {
        return a;
    } else {
        return b;
    }
}
//按照x坐标排序的比较函数
int compare_x(const void* a, const void* b) {
    point* p1 = (point*)a;
    point* p2 = (point*)b;
    if (p1->x < p2->x) {
        return -1;
    } else if (p1->x > p2->x) {
        return 1;
    } else {
        return 0;
    }
}
//按照y坐标排序的比较函数
int compare_y(const void* a, const void* b) {
    point* p1 = (point*)a;
    point* p2 = (point*)b;
    if (p1->y < p2->y) {
        return -1;
    } else if (p1->y > p2->y) {
        return 1;
    } else {
        return 0;
    }
}
//暴力法求解最近点对，适用于点数较少的情况
pair brute_force(point* points, int n) {
    pair min_pair; //最近点对
    min_pair.dist = INFINITY; //最近点对距离初始化为无穷大
    for (int i = 0; i < n; i++) { //遍历每个点
        for (int j = i + 1; j < n; j++) { //与后面的点进行比较
            double dist = distance(points[i], points[j]); //计算两点之间的距离
            if (dist < min_pair.dist) { //如果发现更近的点对，更新最近点对和最近点对距离
                min_pair.p1 = points[i];
                min_pair.p2 = points[j];
                min_pair.dist = dist;
            }
        }
    }
    return min_pair; //返回最近点对
}
//分治法求解最近点对，适用于点数较多的情况
pair divide_and_conquer(point* points, int n) {
    pair min_pair; //最近点对
    //如果点数小于等于3，直接用暴力法求解
    if (n <= 3) {
        return brute_force(points, n);
    }
    //将n个点按照x坐标排序，然后从中间划分为两个子集，分别求解左右两边的最近点对
    qsort(points, n, sizeof(point), compare_x); //按照x坐标排序
    int mid = n / 2; //中间位置的索引
    point mid_point = points[mid]; //中间位置的点
    pair left_pair = divide_and_conquer(points, mid); //求解左边子集的最近点对
    pair right_pair = divide_and_conquer(points + mid, n - mid); //求解
    //右边子集的最近点对
    min_pair = min(left_pair, right_pair); //比较左右两边的最近点对，取较小者作为当前的最近点对
    //在中间区域内寻找可能存在的更近的点对，即在距离中线不超过当前最近点对距离的范围内，找出所有满足条件的点，并按照y坐标排序
    point* strip = (point*)malloc(n * sizeof(point)); //创建一个动态数组，用于存放满足条件的点
    int size = 0; //记录满足条件的点的个数
    for (int i = 0; i < n; i++) { //遍历每个点
        if (fabs(points[i].x - mid_point.x) < min_pair.dist) { //如果该点距离中线不超过当前最近点对距离
            strip[size++] = points[i]; //将该点加入到动态数组中
        }
    }
    qsort(strip, size, sizeof(point), compare_y); //按照y坐标排序
    //对于每个点，只需与它后面的7个点进行比较，如果发现更近的点对，则更新当前最近点对
    for (int i = 0; i < size; i++) { //遍历每个点
        for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min_pair.dist; j++) { //与后面的7个点进行比较
            double dist = distance(strip[i], strip[j]); //计算两点之间的距离
            if (dist < min_pair.dist) { //如果发现更近的点对，更新最近点对和最近点对距离
                min_pair.p1 = strip[i];
                min_pair.p2 = strip[j];
                min_pair.dist = dist;
            }
        }
    }
    free(strip); //释放动态数组的内存空间
    return min_pair; //返回最近点对
}
//主函数，用于测试代码
int main() {
    //创建一个测试用例，包含6个点
    point points[] = {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}};
    int n = sizeof(points) / sizeof(points[0]); //计算点的个数
    pair result = divide_and_conquer(points, n); //调用分治法求解最近点对
    printf("The closest pair is (%.2f, %.2f) and (%.2f, %.2f), and the distance is %.2f.\n", result.p1.x, result.p1.y, result.p2.x, result.p2.y, result.dist); //打印结果
    return 0;
}