//     program anneal
//
//     Copyright 2001 J. Makino
#include "cpgplot.h"
#include  <stdlib.h>
#include  <stdio.h>
#include  <math.h>
#include  <iostream>

using namespace std;

#define VLEN 2
#include "vector.h"

#define TFACTR 0.9

inline double distance(mvector x[],
		       int    order[],
		       int    i1,
		       int    i2)
{
    mvector x1 = x[order[i1]];
    mvector x2 = x[order[i2]];
    return sqrt((x1-x2)*(x1-x2));
}

double reversal_cost(mvector x[],
		     int order[],
		     int ncity,
		     int n[])
{
    double  de;
    n[2]= (n[0]+ncity-1)%ncity;
    n[3]= (n[1]+1)%ncity;
    de = 0;
    de -= distance(x,order,n[0],n[2]);
    de -= distance(x,order,n[1],n[3]);
    de += distance(x,order,n[0],n[3]);
    de += distance(x,order,n[1],n[2]);
    return de;
}

void reverse(int order[],
	     int ncity,
	     int n[])
{
    int nn,j,k,l,itmp;
    
    nn=(1+((n[1]-n[0]+ncity) % ncity))/2;
    for (j=0;j<nn;j++) {
	k = (n[0]+j) % ncity;
	l = (n[1]-j+ncity) % ncity;
	itmp=order[k];
	order[k]=order[l];
	order[l]=itmp;
    }
}

int metropolis(double de,
	       double t)
{
    int success;
    double ran;
    ran = drand48();
    success = (de < 0.0 || ran < exp(-de/t));
    return success;
}

void initgraph()
{
    
    if(cpgopen("") !=1 ) exit(-1);
    cpgask(0);
}

void show_path(mvector x[],
	       int order[],
	       int n,
	       double path,
	       double t,
	       double xmin,
	       double xmax,
	       double ymin,
	       double ymax,
	       int first)
{
    char label[80];
    cpgbbuf();
    if (first == 1){
         cpgpage();
         cpgenv(xmin, xmax, ymin, ymax,1,-2);
    }
    cpgeras();
    cpgbox("bcnst", 0.0, 0, "bcnst", 0.0, 0);
    cpglab("X", "Y", " ");
    sprintf(label,"T = %12.6e, PATH =%15.7f", t, path);
    cpgtext(xmin, ymax*1.05, label);
    cpgmove(x[order[n-1]][0],x[order[n-1]][1]);
    int i;
    for(i=0;i<n;i++){
	int j= order[i] ;
	cpgdraw(x[j][0],x[j][1]);
    }
    cpgebuf();
}

void anneal(mvector x[],
	    int order[],
	    int ncity)
{
    int ans,nover,nlimit,i1,i2;
    int i,j,k,nsucc,nn;
    int n[4];
    double path,de,t;
    
    nover=100*ncity;
    nlimit=10*ncity;
    path=0.0;
    t=1;
    for (i=0;i<ncity-1;i++) {
	path +=  distance(x,order,i,i+1);
    }
    path += distance(x,order,0,ncity-1);
    real minpath = path;
    srand48(12345);
    show_path(x, order, ncity,path,t,  -0.1, 1.1, -0.1, 1.1, 1);

    for (j=1;j<=100;j++) {
	nsucc=0;
	for (k=1;k<=nover;k++) {
	    do{
		n[0]=(int) (ncity*drand48());
		n[1]=(int) ((ncity-1)*drand48());
		if (n[1] >= n[0]) n[1] += 1;
		nn=1+((n[0]-n[1]+ncity-1) % ncity);
	    }while(nn<3);
	    de=reversal_cost(x,order,ncity,n);
	    ans=metropolis(de,t);
	    if (ans) {
		++nsucc;
		path += de;
		reverse(order,ncity,n);
		if (path < minpath){
		    minpath = path;
		    show_path(x, order, ncity,  path, t,-0.1, 1.1, -0.1, 1.1, 0);
		}
	    }
	    if (nsucc >= nlimit) break;
	}
	cerr << "T,path,move= " << t<< " " << path << " " << nsucc << endl;
	t *= TFACTR;
	if ((nsucc == 0) ) {
	    return;
	}
    }
}

#define MAXVECTOR 10000
main()
{
    mvector x[MAXVECTOR];
    int order[MAXVECTOR],nnode,i;
    initgraph();
    cerr << "Enter number of nodes:";
    cin>>nnode;
    cerr << "Enter points\n";
    for(i=0;i<nnode;i++){
	cin >> x[i];
	order[i]=i;
    }
    anneal(x,order,nnode);
    show_path(x, order, nnode,  0, 0,-0.1, 1.1, -0.1, 1.1, 0);
    cpgend();
    for(i=0;i<nnode;i++){
	int j;
	j = order[i];
	cout << i << " " << j << " " << x[i] << endl;
    }
}