```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100010;
int n;
double X;
double Y;
struct dat{
ll x;
ll y;
double z;
}a[N];
int cmp(dat x,dat y){
return x.z<y.z;
}
ll ans=10000000000000000;
ll calc(int x){
ll res=0;
for(int i=1;i<=n;i++)
res+=max(abs(a[i].x-a[x].x),abs(a[i].y-a[x].y));
return res;
}
int main(){
srand((unsigned long long)(new char)^(19260817));
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
X+=a[i].x;
Y+=a[i].y;
}
X/=n;
Y/=n;
for(int i=1;i<=n;i++)
a[i].z=max(fabs(1.0*a[i].x-X),fabs(1.0*a[i].y-Y));
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
ans=min(ans,calc(i));
if((double)clock()/CLOCKS_PER_SEC>=0.98)
break;
}
cout<<ans;
return 0;
}
```
by MeowScore @ 2022-11-12 15:05:50
一种新的思路
by qlzx74lyc41 @ 2022-11-12 15:07:23
这个和随机化没关系了吧,应该是启发式(人类智慧)+卡时,而且是出于数据性质做的应该很难卡,目前还没看出来构造
by Rnfmabj @ 2022-11-12 16:46:20
~~采访一下,您这个 srand 的意图是什么~~
好人类智慧的乱搞 orz
by StarLbright40 @ 2022-11-12 17:13:41
为什么 ```srand``` 放这么危险的数
by Yizhixiaoyun @ 2022-11-12 17:44:52
@[StarLbright40](/user/128570)
草,直接在退火代码上改的忘删了()
by MeowScore @ 2022-11-12 18:28:20
@[Yizhixiaoyun](/user/590864) ~~这只是我喜欢的一个质数,说它危险的人都是自己思想极其危险~~
by MeowScore @ 2022-11-13 19:16:00
@[LKawaii](/user/140360) 求助,MLE大帝的文章在哪
by ppip @ 2022-11-17 20:07:20
@[ppip](/user/374433) 在 听取MLE声一片 的博客里
by MeowScore @ 2022-11-17 20:08:35