1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<ctime> 5 #include<iostream> 6 #include<algorithm> 7 #include<queue> 8 #include<set> 9 #define inf (0x7fffffff) 10 #define l(a) ((a)<<1) 11 #define r(a) ((a)<<1|1) 12 #define b(a) (1<<(a)) 13 #define T_min (1e-8) 14 #define R (0.99999) 15 #define e (2.718281828459045) 16 #define pi (3.14159265358979323846) 17 #define rep(i,a,b) for(int i=a;i<=(b);i++) 18 #define clr(a) memset(a,0,sizeof(a)) 19 typedef long long ll; 20 typedef unsigned long long ull; 21 using namespace std; 22 int readint(){ 23 int t=0,f=1;char c=getchar(); 24 while(!isdigit(c)){ 25 if(c=='-') f=-1; 26 c=getchar(); 27 } 28 while(isdigit(c)){ 29 t=(t<<3)+(t<<1)+c-'0'; 30 c=getchar(); 31 } 32 return t*f; 33 } 34 const int maxn=200009; 35 int n,opt,tmp,pre,del,path[2][maxn]; 36 double T=1e5,d[maxn]; 37 struct node{ 38 double x,y; 39 inline bool operator<(const node A)const{ 40 return x<A.x||(x==A.x&&y<A.y); 41 } 42 }X[maxn]; 43 int dis(int i,int j){ 44 return int(sqrt((X[i].x-X[j].x)*(X[i].x-X[j].x)+(X[i].y-X[j].y)*(X[i].y-X[j].y))); 45 } 46 int f(int t){ 47 int s=0; 48 rep(i,2,n+1) s+=dis(path[t][i-1],path[t][i]); 49 return s; 50 } 51 void newway(){ 52 int type=rand()%3,a=rand()%(n-1),b=rand()%(n-1); 53 while(a==b) a=rand()%(n-1);a+=2;b+=2; 54 if(a>b) swap(a,b); 55 if(type==0){ 56 rep(i,1,n+1) path[opt^1][i]=path[opt][i]; 57 swap(path[opt^1][a],path[opt^1][b]); 58 }else if(type==1){ 59 rep(i,1,a-1) path[opt^1][i]=path[opt][i]; 60 rep(i,a,b) path[opt^1][i]=path[opt][a-i+b]; 61 rep(i,b+1,n+1) path[opt^1][i]=path[opt][i]; 62 }else{ 63 rep(i,1,a-1) path[opt^1][i]=path[opt][i]; 64 path[opt^1][a]=path[opt][b]; 65 rep(i,a+1,b) path[opt^1][i]=path[opt][i-1]; 66 rep(i,b+1,n+1) path[opt^1][i]=path[opt][i]; 67 } 68 } 69 void cal(){ 70 int ans,cnt=0; 71 srand(time(NULL)); 72 rep(i,1,n) path[opt][i]=i;path[opt][n+1]=1;ans=pre=f(opt); 73 while(T>T_min){ 74 cnt++;if(cnt>1e6) break; 75 newway(); 76 tmp=f(opt^1);del=tmp-pre; 77 ans=min(ans,tmp); 78 if(del<0){ 79 opt^=1;pre=tmp; 80 }else if(rand()*rand()/32767.0/32767.0<pow(e,-del/T)){ 81 opt^=1;pre=tmp; 82 } 83 T*=R; 84 } 85 cout<<cnt<<endl; 86 printf("%d ",ans); 87 } 88 int main(){ 89 freopen("#input.txt","r",stdin); 90 //freopen("#output.txt","w",stdout); 91 n=readint(); 92 rep(i,1,n){ 93 X[i].x=readint();X[i].y=readint(); 94 } 95 cal(); 96 fclose(stdin); 97 //fclose(stdout); 98 return 0; 99 }