随机旋转，按横坐标排序后枚举每个点与其后面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 ;