题解 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（按顺序）更新答案  ```cpp #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++的三角函数应该为弧度制，谢谢，现已改正。 ### 如果对你有帮助不妨点个赞。