输入格式: 输入第一行给出一个正整数n,表示平面上的点数。随后n行,每行给出一个实数对,每个实数对表示一个点的纵横坐标值,其中第1数表示横坐标,第2数表示纵坐标。 输出格式: 输出最近点对中两个点的坐标和它们之间的距离。如果 x1+y1<=x2+y2则按 (x1,y1),(x2,y2),miniDist=Distance 输出结果,否则按 (x2,y2),(x1,y1),miniDist=Distance 输出结果c语言
时间: 2024-03-07 22:47:28 浏览: 69
以下是按照题目格式要求的C语言程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct point {
double x;
double y;
} Point;
double distance(Point p1, Point p2) {
double dx = p1.x - p2.x;
double dy = p1.y - p2.y;
return sqrt(dx * dx + dy * dy);
}
int compare(const void *a, const void *b) {
Point *p1 = (Point*)a;
Point *p2 = (Point*)b;
if (p1->x != p2->x) {
return p1->x > p2->x;
} else {
return p1->y > p2->y;
}
}
double min(double a, double b) {
return a < b ? a : b;
}
double closest_pair(Point *points, int left, int right) {
if (left == right) {
return INFINITY;
} else if (left + 1 == right) {
return distance(points[left], points[right]);
}
int mid = (left + right) / 2;
double d1 = closest_pair(points, left, mid);
double d2 = closest_pair(points, mid + 1, right);
double d = min(d1, d2);
Point *strip = (Point*)malloc(sizeof(Point) * (right - left + 1));
int count = 0;
for (int i = left; i <= right; i++) {
if (fabs(points[i].x - points[mid].x) < d) {
strip[count++] = points[i];
}
}
qsort(strip, count, sizeof(Point), compare);
for (int i = 0; i < count; i++) {
for (int j = i + 1; j < count && strip[j].y - strip[i].y < d; j++) {
double dist = distance(strip[i], strip[j]);
if (dist < d) {
d = dist;
}
}
}
free(strip);
return d;
}
int main() {
int n;
printf("请输入点的数量:");
scanf("%d", &n);
Point *points = (Point*)malloc(sizeof(Point) * n);
printf("请输入每个点的坐标:\n");
for (int i = 0; i < n; i++) {
printf("第%d个点:", i + 1);
scanf("%lf%lf", &points[i].x, &points[i].y);
}
qsort(points, n, sizeof(Point), compare);
double min_distance = closest_pair(points, 0, n - 1);
Point p1, p2;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n && points[j].x - points[i].x < min_distance; j++) {
double d = distance(points[i], points[j]);
if (d == min_distance && points[i].x + points[i].y <= points[j].x + points[j].y) {
p1 = points[i];
p2 = points[j];
}
}
}
printf("最近点对是(%lf, %lf)和(%lf, %lf),距离为%lf\n",
p1.x, p1.y, p2.x, p2.y, min_distance);
free(points);
return 0;
}
```
这个程序首先会让用户输入点的数量和每个点的坐标,然后使用归并排序将点按照x坐标从小到大排序。接着,程序调用 `closest_pair()` 函数来递归地寻找平面上距离最近的点对,这个函数的实现使用了分治算法和蛮力算法的结合。最后,程序输出距离最近的点对的坐标和距离,并按照题目格式要求的顺序输出。
阅读全文