/*
NAME: Ivan Anev
SCHOOL: SMG
ID: A5
PROG: travel


ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕНТ02 - 16 ноемв░и 2002
ТЕМА ЗА 11-12 КЛАС (ГРУПА A)

Зада╖а 1. ОБИКОЛКА

Хо░а о▓ ░азли╖ни п░о┤е▒ии (по╣ал╝они, ░азно▒ва╖и на ▒▓оки по домове▓е,
▓║░гов╢и и ▓.н.) ╖е▒▓о ▒а изп░авени п░ед ▒ледна▓а зада╖а: ▓е ▓░┐бва да ▓░║гна▓
о▓ ▓о╖ка, ▒║о▓ве▓на на ░або▓но▓о им м┐▒▓о (по╣ен▒ка ▒▓ан╢и┐, магазин, ▒клад
или о┤и▒ на ┤и░ма▓а), да по▒е▓┐▓ н┐колко д░│ги ▓о╖ки, к║де▓о ▒а ░азположени
клиен▓и▓е им и да ▒е в║░на▓ в на╖ална▓а ▓о╖ка на обиколка▓а. Нека ▓о╖ки▓е,
п░ез кои▓о ▓░┐бва да мине обиколка▓а ▒а озна╖ени ▒ ╖и▒ла▓а о▓ 1 до N, ка▓о
на╖ална▓а ▓о╖ка е озна╖ена ▒ 1. За в▒еки две ▓о╖ки, кои▓о ▓░┐бва да б║да▓
по▒е▓ени (вкл╛╖и▓елно и на╖ална▓а ▓о╖ка на обиколка▓а) е изве▒▓но ╢┐ло ╖и▒ло Ц
░аз▒▓о┐ние межд│ две▓е ▓о╖ки (в░еме за изминаване на ▓ова ░аз▒▓о┐ние или
н┐каква д░│га ╢ена за изминаване▓о м│). Н┐ма ▒║мнение, ╖е колко▓о по-к░а▓ка
(по-б║░за, по-ев▓ина) е обиколка▓а, ▓олкова по-доб░е. За ▒║жаление, доб░е
изве▒▓но е, ╖е да ▒е наме░и най-доб░а▓а в║зможна обиколка не е никак ле▒но,
ако б░о┐▓ на ме▒▓а▓а, кои▓о ▓░┐бва да б║да▓ по▒е▓ени е до▒▓а▓║╖но гол┐м.
Ва╕а▓а зада╖а е да напи╕е▓е п░ог░ама TRAVEL.EXE, ко┐▓о да опи▓а да наме░и за
о▓п│▒на▓о▓о й в░еме колко▓о може по-доб░о ░е╕ение.

Данни▓е ╣е б║да▓ зададени в ▓ек▒▓ов ┤айл, кой▓о ва╕а▓а п░ог░ама ╣е п░о╖е▓е о▓
▒▓анда░▓ни┐ ▒и в╡од. В п║░ви┐ ░ед на в╡одни┐ ┤айл ╣е б║де зададено ╢┐ло▓о
╖и▒ло N (3 < N < 200) Ц б░о┐▓ на ▓о╖ки▓е, кои▓о ▓░┐бва да б║да▓ по▒е▓ени,
вкл╛╖и▓елно на╖ална▓а. В▒еки о▓ ▒ледва╣и▓е N ░еда ╣е ▒║д║░жа ╢ело╖и▒лени▓е
коо░дина▓и (░азделени ▒ ин▓е░вал) на една о▓ ▓о╖ки▓е Ц в ░еда на номе░а▓а им.
Раз▒▓о┐ние▓о межд│ две ▓о╖ки е ▓.н. ман╡а▓║н▒ко ░аз▒▓о┐ние. За ▓о╖ки▓е ▒
коо░дина▓и (x1,y1) и (x2,y2) ▓о ▒е п░е▒м┐▓а по ┤о░м│ла▓а |x1Цx2| + |y1Цy2|.
В▒и╖ки коо░дина▓и ▒а нео▓░и╢а▓елни ╢ели ╖и▒ла, не над╡в║░л┐╣и 10000.

Из╡одни┐▓ ┤айл ▓░┐бва да б║де изведен на ▒▓анда░▓ни┐ из╡од. Той ▓░┐бва да
▒║д║░жа един ░ед ▒ пе░м│▓а╢и┐▓а на ╖и▒ла▓а о▓ 1 до N, ░азделени ▒ по един
ин▓е░вал Ц наме░ена о▓ п░ог░ама▓а обиколка.

О╢енка▓а на ░ез│л▓а▓а о▓ ░або▓а▓а на Ва╕а▓а п░ог░ама▓а в║░╡│ в▒еки ▓е▒▓ ╣е
б║де изв║░╕ена ▒лед ▒░авн┐ване ▒ ░ез│л▓а▓и▓е на д░│ги▓е ▒║▒▓еза▓ели.
П░ог░ами▓е по▒▓░оили най-доб░а обиколка ╣е пол│╖а▓ п║лни┐ б░ой ▓о╖ки за ▓е▒▓а,
а в▒┐ка о▒▓анала п░ог░ама Ц ╖а▒▓ о▓ п║лни┐ б░ой, п░опо░╢ионална на д║лжина▓а
на наме░ено▓о ░е╕ение.

П░име░

В╡од              Из╡од (един о▓ в║зможни▓е)

6                 1 4 6 5 3 2
0 0
40 0
25 5
20 10
40 20
10 20

РЕШЕНИЕ:

Зада╖а 1 е изве▒▓на под име▓о Узада╖а за ▓║░гов▒ки┐ п║▓никФ. С║╣о ▓ака е
изве▒▓но, ╖е не е наме░ено ░е╕ение ░азли╖но о▓ п║лно▓о из╖е░пване, кое▓о да
░е╕ава зада╖а▓а. На ▒║▒▓езание▓о ▒е и▒ка╕е да ▒е наме░и колко▓о ▒е може
по-доб░о ░е╕ение в ░амки▓е на 5 ▒ек│нди.

К║м зада╖а▓а има н┐колко под╡ода. Има н┐колко изве▒▓ни п░иближени ░е╕ени┐
на░е╖ени ап░ок▒има╢ии, кой▓о нами░а▓ ░е╕ение ▒ н┐как║в кое┤и╢иен▓ k по-ло╕о о▓
най-доб░о▓о, ка▓о н┐кой о▓ ▒║▒▓еза▓ели▓е ░еализи░а╡а н┐кои о▓ ▓┐╡. Едно о▓ ▓┐╡
е да ▒е нап░ави об╡ождане в д║лбо╖ина на минимално об╡ва╣а╣о д║░во на ▓о╖ки▓е,
кое▓о ╣е ни даде ░ед за по▒е╣аване на ▓о╖ки▓е; за ▓ова ░е╕ение е в┐░но, ╖е
кое┤и╢иен▓║▓ k винаги е не по-гол┐м о▓ 2 и обикновено е в ин▓е░вала [1.15,
1.20]. С║╣о ▓ака, много │╖а▒▓ни╢и напи▒а╡а много ле▒ен greedy алго░и▓║м, кой▓о
на в▒┐ка ▒▓║пка о▓ ▓ек│╣и┐ в░║╡ о▓ива в║в най-близки┐ не по▒е▓ен в░║╡.

Д░│г под╡од (░еализи░ан о▓ мен) е п║лно▓о из╖е░пване, ка▓о ▓░┐бва да ▒е взема▓
под внимание н┐колко момен▓а. Алго░и▓║м║▓ п░обва о▓ ▓ек│╣и┐ в░║╡ да о▓иде в║в
в▒еки в░║╡ кой▓о не е по▒е▓ен и о▓ ▓ози, в кой▓о е о▓и╕║л о▓ново п░обва да
о▓иде в║в в▒еки не по▒е▓ен и ▓.н. С║╣о ▓ака об╡ождане▓о на ▒║▒едни▓е в║░╡ове
▒▓ава в ░ед на о▓дале╖ено▒▓ о▓ него, ка▓о п░║в ▒е по▒е╣ава ▓ози, кой▓о е
най-близо. Мака░ по▒ледно▓о да дава до▒▓а доб░о подоб░ение ка▓о ╢┐ло п║лно▓о
из╖е░пване има един гол┐м недо▒▓а▓║к. П░и гол┐м б░ой в║░╡ове алго░и▓║м║▓ ╣е
нап░ави в▒и╖ки в║зможни об╡ождани┐ на по▒ледни▓е 20-30 в║░╡а, но п░и ло╕ избо░
в на╖ало▓о ▓ова н┐ма да наме░и много по-доб░о ░е╕ение. В ▓акива ▒л│╖ай ▒е
използва ле▒ен за ░еализи░ане под╡од (не ░еализи░ан о▓ мен по в░еме на
▒║▒▓езание▓о по░ади лип▒а на желание), п░и кой▓о ▒лед оп░еделен пе░иод о▓
в░еме (нап░име░ 0.1 ▒ек) алго░и▓║ма ▒е в░║╣а (1/2*N) ▒▓║пки назад, а ▒лед
в▒┐ка една ▒ек│нда ▒е в░║╣а до п║░ви┐ в░║╡. Така може да ▒е поп░ави ло╕ избо░
в на╖ало▓о. Не ░еализи░ане▓о на по▒ледни┐ под╡од за гол┐м б░ой в║░╡ове не дава
много по-доб░о ░е╕ение о▓ по▒о╖ени┐ по-го░е greedy алго░и▓║м.
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>

#define MAXN 256

typedef struct Point TPoint;
struct Point {
	int x, y;
};

typedef struct Vex TVex;
typedef struct Edge TEdge;

struct Vex {
	int v, b;
	TEdge *edges;
};

struct Edge {
	int v, w;
	TEdge *next;
};

int n;
TPoint pt[MAXN];
TVex vs[MAXN];
clock_t s;

int bp;
int path[MAXN];

void readf(void);
void solve(void);
void writef(void);

int main(void) {
	readf();
	solve();
	writef();

	return 0;
}

void readf(void) {
/*	FILE *fin; */
	int i;

/*	fin = fopen("travel.in", "r");
	fscanf(fin, "%d", &n);
	for (i = 0; i < n; ++i)
		fscanf(fin, "%d %d\n", &pt[i].x, &pt[i].y);
	fclose(fin);
*/

	scanf("%d", &n);
	for (i = 0; i < n; ++i)
		scanf("%d%d", &pt[i].x, &pt[i].y);
}

void solve(void) {
	int i, j;

	void add_edge(int a, int b);
	int dfs(int v, int cp, int len);

	s = clock();

	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			if (i != j)
				add_edge(i, j);

	bp = INT_MAX;
	dfs(0, 0, 1);
}

void writef(void) {
	int i;

	printf("%d", path[0]+1);
	for (i = 1; i < n; ++i)
		printf(" %d", path[i]+1);
	printf("\n");
}

void add_edge(int a, int b) {
	TEdge *e, **se;

	e = (TEdge*)malloc(sizeof(TEdge));
	e->v = b;
	e->w = abs(pt[a].x - pt[b].x) + abs(pt[a].y - pt[b].y);
	for (se = &vs[a].edges; *se && (*se)->w < e->w; se = &(*se)->next)
		;
	e->next = *se;
	*se = e;
}

int dfs(int v, int cp, int len) {
	TEdge *e;
	int i, u;
	clock_t c;

	if (cp < bp) {
		vs[v].v = 1;
		for (e = vs[v].edges; e; e = e->next)
			if (e->v == 0 && len == n) {
				if (cp + e->w < bp) {
					bp = cp + e->w;
					u = v;
					for (i = n-1; i >= 0; --i) {
						path[i] = u;
						u = vs[u].b;
					}
				}
			}
			else if (vs[e->v].v == 0) {
				c = clock();
				if ((c - s) / 1000.0 > 4.9)
					return 1;
				vs[e->v].b = v;
				if (dfs(e->v, cp + e->w, len+1))
					return 1;
			}
		vs[v].v = 0;
	}

	return 0;
}