随机旋转,按横坐标排序后枚举每个点与其后面5个点的距离取最小值更新答案(算法导论里有提到这个算法)

我这里随机旋转了两次(你想要转几次都行)

记得初始化数据不然排序后的后面几个数据会凑巧有几个点在(0,0)旁可能会把答案更新成与(0,0)之间的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<ctime>
#define INF 9999999999.0
using namespace std;

struct node{
double x,y;
}a[2000010];
int n;
double ans=INF; //初始化答案为一个很大的数

bool cmp(node a,node b){
return a.x<b.x; //按照横坐标排序
}
double len(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++){
double temp;
temp=len(a[i],a[j]);
ans=min(ans,temp);
}
}
}
void around(int ds){
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)); //随机数种子
for (int i=1;i<=200009;i++){
a[i].x=INF;a[i].y=INF; //初始化
}

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",ans);
return 0;
}

旋转公式:

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

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