一维最近点对——C语言代码

以下是使用C语言实现的一维最近点对算法代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_N 100000

typedef struct {
double x;
double y;
} Point;

Point points[MAX_N];
int n;

int cmp(const void* a, const void* b) {
Point* pa = (Point*)a;
Point* pb = (Point*)b;
return pa->x < pb->x ? -1 : 1;
}

double dist(Point p1, Point p2) {
return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

double closest_pair(int left, int right) {
double d = 1e9;
if (left == right) {
return d;
}
if (left + 1 == right) {
return dist(points[left], points[right]);
}
int mid = (left + right) / 2;
double d1 = closest_pair(left, mid);
double d2 = closest_pair(mid + 1, right);
d = fmin(d1, d2);

Point tmp[n];
int k = 0;
for (int i = left; i <= right; i++) {
if (fabs(points[i].x - points[mid].x) < d) {
tmp[k++] = points[i];
}
}
qsort(tmp, k, sizeof(Point), cmp);
for (int i = 0; i < k; i++) {
for (int j = i + 1; j < k && tmp[j].y - tmp[i].y < d; j++) {
double dis = dist(tmp[i], tmp[j]);
d = fmin(d, dis);
}
}
return d;
}

int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lf%lf", &points[i].x, &points[i].y);
}
qsort(points, n, sizeof(Point), cmp);

double ans = closest_pair(0, n - 1);
printf("%.2f", ans);
return 0;
}