Hide

Tivoli

Lisa er kommet til Tivoli og har bestemt sig for at prøve $N$ forlystelser en gang hver. Hver forlystelse er anlagt to gange, og de to anlæg er lige gode; totalt findes der altså $2N$ anlæg. Givet positionerne for samtlige anlæg hjælp Lisa med at planlægge, hvilke $N$ anlæg hun skal vælge og i hvilken rækkefølge for at minimere den strækning, hun skal gå for at besøge alle $N$ forlystelser.

Desuden begynder og slutter hun ved indgangen. Indgangen er i origo, $(0,0)$.

I eksemplet forneden er $N=3$, og de to anlæg af forlystelse $f$ kaldes $f_1$ og $f_2$. Lisa går fra indgangen til $2_2$, derfra til $1_1$, så til $3_1$ og endelig tilbage til indgangen. Den totale strækning er $14{,}23345$.

\includegraphics[width=0.5\textwidth ]{img/tivoli-sample-img.pdf}

Indlæsning

Første linje består af heltallet $N$, som angiver antallet af forlystelser, som Lisa vil besøge ($1 \le N \le 15$). Derefter følger $N$ linjer, hvoraf første linje beskriver forlystelse nummer $1$, anden linje beskriver forlystelse nummer $2$, osv. Hver linje indeholder fire heltal: $x$- og $y$-koordinaterne for denne forlystelses første anlæg efterfulgt af $x$- og $y$-koordinaterne for denne forlystelseforlystelses anlæg. Koordinaternes absolutværdi er mindre end en million.

Intet anlæg er på samme plads som noget andet. Intet anlæg er i origo.

Udskrift

Udskriftens første linje skal bestå af et decimaltal skrevet med decimalpunktum: hvor langt Lisa skal gå. Derefter skal der komme $N$ linjer med to heltal på hver, forlystelsesnummeret (mellem $1$ og $N$) og anlægsnummeret ($1$ eller $2$).

Den første af de $N$ linjer fortæller altså, hvilket anlæg hun skal besøge først, og den sidste linje fortæller, hvilket anlæg hun skal besøge sidst. Hvis der findes flere veje med lige kort strækning (fx ved at følge en løsning baglæns), kan du vælge hvilken som helst af dem. Læg mærke til at det først udskrevne decimaltal skal tage hensyn til, at Lisa skal begynde og slutte ved indgangen.

Den relative fejl skal være mindre end $10^{-5}$.

Sample Input 1 Sample Output 1
3
3 5 1 -1
-2 0 0 4
4 4 0 6
14.233345
2 2
1 1
3 1
CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in