题解 P1429 【平面最近点对（加强版）】

· · 题解

该算法的基本步骤是：

1. 随机旋转

2. 按横坐标排序后枚举每个点与其后面5个点的距离取最小值更新答案。

旋转公式（旋转中心为（x2,y2））：

x=(x1-x2)cos(θ)-(y1-y2)sin(θ)+x2;

y=(x1-x2)sin(θ)+(y1-y2)cos(θ)+y2;

注意θ为弧度(在C++中三角函数以弧度进行运算)

如果不旋转会怎么出错呢？

如图A点会与B、C、D、E、F（按顺序）更新答案，但是G应该是离A最近的点。

旋转可以很好地解决这个问题。如下图：A点会与G、F、D、B、C（按顺序）更新答案


#include<bits/stdc++.h>
#define pi acos(-1.0)
using namespace std;
struct node{
    double x,y;
}a[200005];
int n;
double ans=1e15;//初始化答案

bool cmp(node a,node b){
    return a.x<b.x;//按照横坐标排序 
}
double dis(node a,node b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));//计算两点之间距离 
}
void calc(){
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=i+5&&j<=n;j++)
            ans=min(ans,dis(a[i],a[j]));
}
void around(double ds){
    ds=ds/180.0*pi;//角度转换为弧度 
    for (int i=1;i<=n;i++){
        double x=a[i].x,y=a[i].y;//旋转前的点 
        double xn,yn;//旋转后的点 
        double xyu=0.0,yyu=0.0;  //旋转中心 
        xn=(x-xyu)*cos(ds)-(y-yyu)*sin(ds)+xyu;
        yn=(x-xyu)*sin(ds)+(y-yyu)*cos(ds)+yyu;
        a[i].x=xn,a[i].y=yn;
    }
    sort(a+1,a+1+n,cmp);//排序 
    calc();//计算 
}

int main(){
    srand(time(NULL));
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    around(0);//将原图像进行排序并枚举每个点与其后五个点比较 
    around(rand()%360);//将图像随机（0°~359°）旋转  并排序 计算 
    around(rand()%360);//将图像随机（0°~359°）旋转  并排序 计算 
    printf("%.4lf\n",ans);
    return 0;
}

upd 11/4：有评论指出C++的三角函数应该为弧度制，谢谢，现已改正。

如果对你有帮助不妨点个赞。