mission

Mission

== include(page="template/taskheader" task_id="mission") ==

Zeratul a primit de la Tassadar o misiune foarte importantă: trebuie să distrugă $N$ centre de comandă ale terranilor, numerotate de la $0$ la $N – 1$, cunoscând coordonatele $x$ şi $y$ din plan ale acestora. Iniţial, Zeratul este teleportat în centrul de comandă cu numărul $0$, unde va trebui să se întoarcă după ce îşi îndeplineşte misiunea şi distruge toate celelalte centre de comandă. De asemenea, ştim că Zeratul se poate deplasa între două centre de comandă numai în linie dreaptă. Terranii sunt prevăzători şi au minat terenul corespunzător întregului plan $XOY$. Ca urmare, Zeratul poate să treacă printr-un punct din plan cel mult odată (cu excepţia centrului de comandă $0$, de unde va fi recuperat la finalul misiunii).

Zeratul a primit de la Tassadar o misiune foarte importantă: trebuie să distrugă $N$ centre de comandă ale terranilor, numerotate de la $0$ la $N – 1$, cunoscând coordonatele $x$ şi $y$ din plan ale acestora. Iniţial, Zeratul este teleportat în centrul de comandă cu numărul $0$, unde va trebui să se întoarcă după ce îşi îndeplineşte misiunea şi distruge toate celelalte centre de comandă. Zeratul se poate deplasa între două centre de comandă numai în linie dreaptă. Terranii sunt prevăzători şi au minat terenul corespunzător întregului plan $XOY$. Ca urmare, el poate să treacă printr-un punct din plan cel mult odată (cu excepţia centrului de comandă $0$, de unde va fi recuperat la finalul misiunii).

Zeratul vă promite o recompensă de $100$ de puncte, dacă îi spuneţi în ce ordine să distrugă cele $N$ centre de comandă, astfel încât la final să se întoarcă în centrul de comandă cu indicele $0$ şi să nu treacă prin acelaşi punct de mai multe ori.
h2. Date de intrare

Fişierul de intrare $mission.in$ conţine pe prima linie numărul întreg $N$, semnificând numărul de centre de comandă pe care trebuie să le distrugă Zeratul. Pe următoarele $N$ linii se află câte două numere întregi $x$ şi $y$, reprezentând coordonatele celor $N$ centre de comandă.

Fişierul de intrare $mission.in$ conţine pe prima linie numărul întreg $N$, semnificând numărul de centre de comandă pe care trebuie să le distrugă Zeratul. Pe următoarele $N$ linii se află câte două numere întregi $x{~i~}$ şi $y{~i~}$, reprezentând coordonatele celor $N$ centre de comandă.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ N ≤ 1$
* $-1.000.000.000 ≤ x{~i~}, y{~i~} ≤ 1.000.000.000$

* $3 ≤ N ≤ 1000$
* $-1.000.000 ≤ x{~i~}, y{~i~} ≤ 1.000.000$

* dacă Zeratul trece printr-un centru de comandă, el este obligat să-l distrugă (deoarece nu mai poate trece a doua oară prin acel centru şi nu şi-ar îndeplini misiunea); acest lucru este valabil inclusiv pentru centrul de comandă $0$
* după ce distruge al $N$-lea centru de comandă din traseul indicat de voi, el se va întoarce în centrul de comandă $0$, tot în linie dreaptă
* Zeratul nu poate trece printr-un punct de mai multe ori, chiar dacă a distrus toate centrele de comandă
* dacă există mai multe soluţii, se poate afişa oricare

* oricare trei centre de comandă sunt necoliniare

h2. Exemplu
table(example). |_. mission.in |_. mission.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
0 0
1 1
2 0
0 3
2 3
| 0 3 4 1 2

|
h3. Explicaţie

...

Un exemplu de permutare care nu respectă cerinţele este ${0, 4, 3, 2, 1}$, deoarece Zeratul trece prin punctul $(1, 1.5)$ de două ori.
Un alt exemplu de permutare care nu respectă cerinţele este ${2, 1, 4, 3, 0}$, deoarece Zeratul trece, iniţial, prin centrul de comandă $0$ fără să-l distrugă.

== include(page="template/taskfooter" task_id="mission") ==