#include <ilcplex/ilocplex.h>
#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#include <limits>

#define DEBUG 2

using namespace std;
ILOSTLBEGIN

typedef IloInt itype;

int edge_id(int n, int u, int v){
	if(u == v) return -1;
	int i = min(u, v); int j = max(u, v);
	return i*(2*n - i - 1)/2 + (j-i-1);
}


ILOLAZYCONSTRAINTCALLBACK2(EliminacaoSubCiclo, IloBoolVarArray, X, int, n){
	IloEnv masterEnv = getEnv();

	vector<int> routeFromZero;

	int current = 0;
	int past = -1;

	do{
		for (int v = 0; v < n; v++) {
			if(v != past && v != current && getValue(X[edge_id(n, current, v)]) > 0.999){
				routeFromZero.push_back(v);
				past = current;
				current = v;
				break;
			}
		}
	}while(current != 0);

	if(DEBUG >= 2){
		cout << "Route from zero: " << endl;
		for(int v = 0; v < routeFromZero.size(); v++){
			cout << routeFromZero[v] << " ";
		}
		cout << endl;
	}

	if(routeFromZero.size() == n) return;

	IloExpr expr(masterEnv);
	for(int v = 0; v < routeFromZero.size(); v++){
		for(int u = v+1; u < routeFromZero.size(); u++){
			//cout << getValue(X[edge_id(n, routeFromZero[v], routeFromZero[u])]) << " + ";
			expr += X[edge_id(n, routeFromZero[u], routeFromZero[v])];
		}
	}
	//cout << endl;

	add(expr <= ((int) routeFromZero.size() - 1));
	//cout << expr << " <= " << ((int) routeFromZero.size() - 1) << endl;


	return;
}

int main(int argc, char * argv[]){
	if(argc < 3){
		cout << "Uso incorreto, tente " << argv[0] << " arquivo_entrada arquivo_saida" << endl;
		return -1;
	}

	IloEnv env;
	try {
		int n;
		ifstream entrada;
		entrada.open(argv[1]);
		ofstream saida;
		saida.open(argv[2]);
		entrada >> n;

		vector<double> x(n);
		vector<double> y(n);

		for (int p = 0; p < n; p++) {
			entrada >> x[p] >> y[p];
		}
		entrada.close();

		int m = (n*n - n) / 2;
		IloIntArray costs(env, m);

		for (int u = 0; u < n; u++) {
			for (int v = u+1; v < n; v++) {
				int edge = edge_id(n, u, v);
				//O Calculo do custo da aresta é assim distancia euclidiana dos pontos doubles
				// e depois pega o piso.
				costs[edge] = floor(sqrt(pow(x[u] - x[v], 2) + pow(y[u] - y[v], 2)));
			}
		}
		if(DEBUG >= 2){
			for (int u = 0; u < n; u++) {
				for (int v = u+1; v < n; v++) {
					int edge = edge_id(n, u, v);
					cout << costs[edge] << " ";
				}
				cout << endl;
			}
		}

		IloBoolVarArray X(env, m);
		IloModel model(env);


		for(int u = 0; u < n; u++){
			IloExpr expr(env);
			for (int v = 0; v < n; v++) {
				if(u == v) continue;
				expr += X[edge_id(n, u, v)];
			}
			model.add(expr == 2);
		}

		model.add(IloMinimize(env, IloScalProd(costs, X)));
		IloCplex cplex(env);
		cplex.extract(model);

		cplex.use(EliminacaoSubCiclo(env, X, n));

		//cplex.setOut(env.getNullStream());
		cplex.setParam(IloCplex::Param::DetTimeLimit, 600*1000);
		cplex.setParam(IloCplex::Param::MIP::Limits::TreeMemory, 4000);
		cplex.solve();

		saida << cplex.getObjValue() << endl;
		cout << cplex.getStatus() << endl;

		int current = 0;
		int past = -1;
		do{
			for (int v = 0; v < n; v++) {
				if(v != past && v != current && cplex.getValue(X[edge_id(n, current, v)]) > 0.999){
					saida << v << " ";
					past = current;
					current = v;
					break;
				}
			}
		}while(current != 0);


		saida << endl;

		if(DEBUG >= 2){
			for (int u = 0; u < n; u++) {
				for (int v = u+1; v < n; v++) {
					int edge = edge_id(n, u, v);
					cout << cplex.getValue(X[edge_id(n, current, v)]) << " ";
				}
				cout << endl;
			}
		}


	}
	catch (IloException& ex) {
		cerr << "Error: " << ex << endl;
	}
	catch (...) {
		cerr << "Error" << endl;
	}
	env.end();
	return 0;
}