模拟退火求助142分

黑影洞人 @ 2022-08-07 11:52:09

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#define int long long
#define N 500000 
using namespace std;
const double eps=1e-9,pi=3.14;
struct node{
    double x,y;
    void in(){scanf("%lf%lf",&x,&y);}
    double dis(node a){return (a.x-x)*(a.x-x)+(a.y-y)*(a.y-y);}
    bool operator<(const node &a)const{return x*y<a.x*a.y;}
}a[N];
int n;
double fi,ans=1e15; 
double calc(double xt){
    xt=(xt/180.0)*pi;
    for(int i=1;i<=n;i++){
        double x=a[i].x,y=a[i].y;
        a[i].x=x*cos(xt)-y*sin(xt);
        a[i].y=x*sin(xt)+y*cos(xt);
    }
    double res=1e15;
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=min(i+5ll,n);j++){
            res=min(res,a[i].dis(a[j]));
        }
    }
    return res;
}
void sa(){
    //printf("%lf\n",fi);
    for(double t=1145;t>eps;t*=0.996){
        double lz=fmod(fi+rand()*t,360.0);
        double now=calc(lz),del=now-ans;
        if(del<0)ans=now,fi=lz;
        else if((-del/t)*RAND_MAX>rand())fi=lz;
        if((double)clock()/CLOCKS_PER_SEC<=0.3){printf("%.0lf\n",ans);exit(0);}
    }
}
signed main(){
    srand(time(0));
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)a[i].in();
    fi=0;
    ans=min(ans,calc(rand()%360));
    sa();
    printf("%.0lf\n",ans);
    return 0;
}

by 麦克斯韦の妖 @ 2022-08-07 12:09:09

加强加强版你还退火，好好写分治吧（

by 黑影洞人 @ 2022-08-07 12:09:55

@麦克斯韦の妖 我过了

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#define int long long
#define N 500000 
using namespace std;
const double eps=1e-9,pi=3.1416;
struct node{
    double x,y;
    void in(){scanf("%lf%lf",&x,&y);}
    double dis(node a){return (a.x-x)*(a.x-x)+(a.y-y)*(a.y-y);}
    bool operator<(const node &a)const{return x*y<a.x*a.y;}
}a[N];
int n;
double fi,ans=1e15; 
double calc(double xt){
    xt=(xt/180.0)*pi;
    for(int i=1;i<=n;i++){
        double x=a[i].x,y=a[i].y;
        a[i].x=x*cos(xt)-y*sin(xt);
        a[i].y=x*sin(xt)+y*cos(xt);
    }
    double res=1e15;
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=min(i+50ll,n);j++){
            res=min(res,a[i].dis(a[j]));
        }
    }
    return res;
}
void sa(){
    for(double t=1145;t>eps;t*=0.996){
        double lz=fmod(fi+rand()*t,360.0);
        double now=calc(lz),del=now-ans;
        if(del<0)ans=now,fi=lz;
        else if((-del/t)*RAND_MAX>rand())fi=lz;
        if((double)clock()/CLOCKS_PER_SEC<=0.34){printf("%.0lf\n",ans);exit(0);}
    }
}
signed main(){
    srand(time(0));
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)a[i].in();
    fi=0;
    ans=min(ans,calc(0));
    ans=min(ans,calc(rand()%360));
    ans=min(ans,calc(rand()%360));
    sa();
    printf("%.0lf\n",ans);
    return 0;
}

by 黑影洞人 @ 2022-08-07 12:10:10

@麦克斯韦の妖 没想到吧

by 麦克斯韦の妖 @ 2022-08-07 12:33:02

@黑影洞人 我当时模拟退火142卡了十几次放弃了

by 黑影洞人 @ 2022-08-07 13:04:44

@麦克斯韦の妖 你可以看看我的