Rước đuốc Olympic

View as PDF

Submit solution

Points: 2.00 (partial)
Time limit: 0.9s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
HAOI 2008 - Day 2 - Author: Lê Đôn Khuê
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Olympic Bắc Kinh ~2008~ đang diễn ra vô cùng sôi nổi và quyết liệt. Ngay từ lúc này, những nhà tổ chức của Olympic London ~2012~ đã tính đến kế hoạch cho lễ rước đuốc của Olympic lần tới. Họ dự định sẽ đi qua ~N~ thành phố. Mỗi thành phố có tọa độ ~(x~, ~y)~ trên mặt phẳng. Kế hoạch của lễ rước đuốc là ngọn đuốc sẽ bắt đầu từ thành phố ~1~, đi lần lượt giữa các thành phố khác mỗi thành phố đúng ~1~ lần rồi quay trở lại thành phố ~1~. Bạn hãy tìm một hành trình để tổng đường đi là nhỏ nhất.

Input

  • Dòng thứ nhất ghi số ~N~.
  • ~N~ dòng tiếp theo, mỗi dòng ghi một cặp số ~(x~, ~y)~ là tọa độ của các thành phố

Output

  • Dòng đầu tiên ghi độ dài của hành trình có đường đi ngắn nhất mà bạn tìm được với ít nhất ~3~ chữ số sau dấu phẩy.
  • Dòng thứ hai ghi ~N~ số bắt đầu bằng số ~1~ và tiếp theo là lần lượt các thành phố trên hành trình.

Giới hạn

  • ~1 \leq N \leq 100~
  • Tọa độ các thành phố có trị tuyệt đối không quá ~10^5~.

Với mỗi test, ban tổ chức có đưa ra một đáp số ~ExpectedResult~. Gọi kết quả của bạn là ~Result~.

  • Nếu ~Result \leq ExpectedResult~ bạn sẽ được 10 điểm.
  • Nếu ~ExpectedResult < Result < 1.5 \times ExpectedResult~ bạn sẽ được ~\max\left(0; 9 - 1.5^{\frac{Result - ExpectedResult}{25}}\right)~
  • Ngoài ra, bạn sẽ không được điểm.

Sample Input

4
0 0
1 0
0 5
1 5

Sample Output

12.0000
1 2 4 3

Note

Kết quả 2

20.1980

1 4 2 3

Kết quả 3

12.1980

1 2 3 4

Với test ví dụ ở trên, với ~ExpectedResult = 12~, output 1 sẽ được ~10~ điểm, output 2 sẽ được ~0~ điểm, output 3 sẽ được ~7.997~ điểm.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.