题解 P1257 【平面上的最接近点对】

· · 题解

思路

因为题目范围是10000，所以我们枚举两个点，求他的距离。时间复杂度是O(n^2)这样是不行的，但因为由i=x点，j=y点 与 i=y点，j=x点是一样的，所以只要把枚举压缩一下，九个一得到时间复杂度为O(n(n-1)/2)的算法，是可以通过的。

枚举代码如下：

for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
        minn=min(minn,sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));//x[i]是第i个点的x坐标，y[i]是滴i个点的y坐标。

代码很短，只有二十几行：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
double minn=2147483647,x[10010],y[10010];//因为输出的是小数，所以我们要用double类型存储。
int n,cnt;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&x[i],&y[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            minn=min(minn,sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));//计算距离并与之前的取最小值。
        }
    }
    printf("%.4lf",minn);//输出保留四位。
    return 0;
}