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

feecle6418 · 2017-11-06 16:03:46 · 题解

【题目名称】寻找平面上的最近点对

【题意大概】给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的。

【标签】枚举法

【重点与坑点】

重点：直接暴力模拟，但是需要优化一下：

• 每次算距离时，不用sqrt，最后再开一次即可。

坑点：并没有的

【代码核心部分】

    double dis(point a,point b){
        return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    }
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            Min=min(Min,dis(a[i],a[j]));//求距离，不要根号
        }
    }
    cout<<fixed<<setprecision(4)<<sqrt(Min);