Fişierul intrare/ieşire:mission.in, mission.outSursăAlgoritmiada 2014, Runda 1
AutorAndrei HeidelbacherAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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ă. 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.

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 xi şi yi, reprezentând coordonatele celor N centre de comandă.

Date de ieşire

În fişierul de ieşire mission.out veţi afişa pe prima linie o permutare de lungime N, reprezentând ordinea în care vor fi distruse cele N centre de comandă.

Restricţii

  • 3 ≤ N ≤ 1000
  • -1.000.000 ≤ xi, yi ≤ 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

Exemplu

mission.inmission.out
5
0 0
1 1
2 0
0 3
2 3
0 3 4 1 2

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ă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?