给出一些整数对,它们表示平面上的点,求所有这些点中距离最近的两个点。 输入格式: 测试数据有多组。对于每组测试,先输入一个整数N,表示点的个数,再输入N个点(以两个整数表示横纵坐标)。若N为0,则表示输入结束。 输出格式: 对于每组测试,输入所有点中距离最短的两点,格式为“(a,b) (c,d)”,其中,a,b,c,d分别表示第一、二个点的横纵坐标。若有多个点对之间距离最短,以先输入者优先(如第一组样例所示)。 输入样例: 4 1 1 2 2 0 0 3 3 4 1 2 0 0 3 6 7 2 0 输出样例: (1,1) (2,2) (1,2) (0,0)
时间: 2024-03-20 12:39:48 浏览: 182
以下是使用暴力枚举法求解的 C++ 代码示例:
```c++
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100010;
struct Point
{
double x, y;
}p[N];
bool cmp(Point a, Point b)
{
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
double dist(Point a, Point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main()
{
int n;
while (cin >> n, n)
{
for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
sort(p, p + n, cmp);
double d = 1e20;
Point a, b;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n && p[j].x - p[i].x < d; j++)
{
double dis = dist(p[i], p[j]);
if (dis < d)
{
d = dis;
a = p[i], b = p[j];
}
}
printf("(%.0f,%.0f) (%.0f,%.0f)\n", a.x, a.y, b.x, b.y);
}
return 0;
}
```
注意事项:
1. 暴力枚举法的时间复杂度为 O(n^2),只适用于点数较少的情况。
2. 在求解过程中,需要使用一个变量 d 记录当前最小距离,以及两个点 a 和 b 记录距离最小的点对。
3. 若有多个点对之间距离最短,按照输入顺序输出即可。
阅读全文