平面最近点对

· · 题解

这道题因为数据水，然后被我用（随机化贪心？）模拟退火（不知道算不算）水过去了，主要是不知道分治怎么写QAQ。。

首先考虑按照x坐标排序。

然后考虑随机一个点。

不难发现，要求最近的点对，实际上，这两个点的横坐标差距会比较小。所以考虑设置一个参数表示对于一个点我们应该随机的其他点在他左右浮动多少。(我写的是12(dela=12))对于一个点随机出来的答案，如果比当前答案优我们就转移from，否则就一定概率转移from(其实这句话完全不需要，只要随机枚举就好了，但加上这句是为了减少重复量)

说实话，我点子低，开着O2才跑过去的。。。

下面给出代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
struct X{
    double x, y;
    bool operator < (const X& a){
        return (x == a.x) ? y < a.y : x < a.x;
    }
}e[N];
double T = 1966, delta = 0.99995, tt = 1e-18;//基本参数
double num = 9999999;//初始答案
int n, dela = 12;//浮动程度（在左右12个的样子浮动）
double check(int x, int y){
    double ans = 0, xx = e[x].x - e[y].x, yy = e[x].y - e[y].y;
    ans = xx * xx + yy * yy;
    return sqrt(ans);
}
int qwq(int x){
    if(rand() % 2) return -x;
    return x;
}
void SA(){
    double t = T;
    int from, to;
    from = rand() % n + 1, to = from + rand() % dela + 1; 
    double DE;
    while(t > tt){
        to = qwq(rand() % dela) + from;//随机出来附近一个点
        if(to < 0) to = 1;//处理溢出
        if(to >= n) to = n;//处理溢出
        if(to == from)//如果相同就重新随机一个点
            continue;
        double ans = check(from, to);
        DE = num - ans;
        if(DE > 0){//如果新答案更优，就接受
            num = ans;
            from = to;
        }
        else if(exp(-DE / t)*RAND_MAX > rand()){//否则以一定概率接受
            from = to;
        }
        t *= delta;
    }
}
void input(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lf%lf", &e[i].x, &e[i].y);
    }
    int qaq = 12;
    num = 999999;
    sort(e + 1, e + n + 1);
    while(qaq--){//跑12遍
        SA();
    }
    printf("%.4lf", num);
    return ;
}
signed main()
{
    srand(time(0));
    input();
    return 0;
}

实际上，上面这个做法并不是特别优秀，因为常常会因为当前答案并不大，但却随机不出一个更好的答案而卡壳。所以最好改下写法—>(把以一定概率接受去掉，改为随机一个端点)这样参数就可以小一点，应该可以快一些

附代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
struct X{
    double x, y;
    bool operator < (const X& a){
        return (x == a.x) ? y < a.y : x < a.x;
    }
}e[N];
double T = 1966, delta = 0.991, tt = 1e-18;
double num = 9999999;
int n, dela = 12;
double check(int x, int y){
    double ans = 0, xx = e[x].x - e[y].x, yy = e[x].y - e[y].y;
    ans = xx * xx + yy * yy;
    return sqrt(ans);
}
int qwq(int x){
    if(rand() % 2) return -x;
    return x;
}
void SA(){
    double t = T;
    int from, to;
    from = rand() % n + 1, to = from + rand() % dela + 1; 
    double DE;
    while(t > tt){
        from = rand() % n + 1; 
        to = qwq(rand() % dela) + from;
        if(to < 0) to = 1;
        if(to >= n) to = n;
        if(to == from)
            continue;
        double ans = check(from, to);
        DE = num - ans;
        if(DE > 0){
            num = ans;
            from = to;
        }
        else if(exp(-DE / t)*RAND_MAX > rand()){
            from = to;
        }
        t *= delta;
    }
}
void input(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lf%lf", &e[i].x, &e[i].y);
    }
    int qwq = 12;
    num = 999999;
    sort(e + 1, e + n + 1);
    while(qwq--){
        SA();
    }
    printf("%.4lf", num);
    return ;
}
signed main()
{
    srand(time(0));
    input();
    return 0;
}

emm，下面一位老哥评论了好像数据加强了的亚子。

我附一个新参数吧...dela = 20, delta = 0.9998，现阶段是可以继续通过的