题解 P1429 【平面最近点对(加强版)】
yuy_
·
·
题解
该算法的基本步骤是:
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++的三角函数应该为弧度制,谢谢,现已改正。
如果对你有帮助不妨点个赞。