给出一些整数对,它们表示平面上的点,求所有这些点中距离最近的两个点。
输入格式:
测试数据有多组。对于每组测试,先输入一个整数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)
解题思路:博主采用了暴力算法,可以去分别求出两点之间的距离,在求的过程中同时进行比较,找出最短的距离,最后再把等于最短距离的两点输出。
注意:
1.由于要多次去求两点的距离,这里将这部分直接写到自定义的float plen函数中。
2.在求最短距离的时候,记得先将前两个点的距离赋值给最短距离(其实直接将负数赋值给min也行,因为距离没有负值)。
3.关于打印,这里是去直接进行遍历求两个点的距离,当这个距离等于这个最短距离min时输出。
代码如下:
#include<stdio.h>
#include<math.h>
float plen(int a, int b, int c, int d)
{
float len = sqrt((a-c)*(a-c) + (b-d)*(b-d));
return len;
}
int main()
{
int n;
int i, j;
int x[10000], y[10000];//将点的横纵坐标分别存在这两个数组中
while(1)
{
scanf("%d", &n);
if(n == 0)
{
break;
}
for(i = 0; i < n; i++)
{
scanf("%d%d", &x[i], &y[i]);
}
//寻找最短距离
float min = plen(x[0], y[0], x[1], y[1]);
for(i = 0; i < n; i++)
{
for(j = i+1; j < n; j++)
{
float len = plen(x[i], y[i], x[j], y[j]);
if(len < min)
{
min = len;
}
}
}
//打印
for(i = 0; i < n; i++)
{
for(j = i+1; j < n; j++)
{
if(min == plen(x[i], y[i], x[j], y[j]))
{
printf("(%d,%d) (%d,%d)\n", x[i], y[i], x[j], y[j]);
break;
}
}
if(min == plen(x[i], y[i], x[j], y[j]))
{
break;
}
}
}
return 0;
}
标签:min,int,PTA,++,len,短距离,两点,plen
From: https://blog.csdn.net/weixin_44190161/article/details/137027742