加强加强版你还退火，好好写分治吧（
by 麦克斯韦の妖 @ 2022-08-07 12:09:09
@[麦克斯韦の妖](/user/255077) 我过了
```cpp
#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:09:55
@[麦克斯韦の妖](/user/255077) 没想到吧
by 黑影洞人 @ 2022-08-07 12:10:10
@[黑影洞人](/user/285617) 我当时模拟退火142卡了十几次放弃了
by 麦克斯韦の妖 @ 2022-08-07 12:33:02
@[麦克斯韦の妖](/user/255077) 你可以看看我的
by 黑影洞人 @ 2022-08-07 13:04:44