CSES - Aybabtu - Kierros
  • Time limit: N/A
  • Memory limit: N/A

Tiedostossa finland.in on 10639 Suomen paikkakunnan koordinaatit. Tehtäväsi on etsiä kierros, joka käy jokaisella paikkakunnalla ja palaa takaisin alkuun. Mitä lyhyempi kierros on, sitä enemmän pisteitä saat.

Syöte

Tiedoston ensimmäisellä rivillä on kokonaisluku nn, paikkakuntien määrä. Paikkakunnat on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Sitten tiedostossa on nn riviä, joista jokainen kuvaa tietyn paikkakunnan koordinaatit. Kullakin rivillä on kaksi desimaalilukua: x- ja y-koordinaatti. Kahden paikkakunnan etäisyys on niiden euklidinen etäisyys.

Palautus

Lähetä tiedosto finland.out, jossa on nn kokonaislukua: paikkakuntien järjestys kierroksessa.

Saat tehtävästä 100p/u\lfloor 100 p/u \rfloor pistettä, missä pp on lyhin mahdollinen kierroksen pituus ja uu on löytämäsi kierroksen pituus.

Esimerkki

Syöte:

3
3.2 5.0
0.0 1.2
3.3 7.0

Tuloste:

2 1 3

Selitys: Kierros on 21322 \rightarrow 1 \rightarrow 3 \rightarrow 2.