ĐƯỜNG ĐI NGẮN NHẤT TRONG HỆ TOẠ ĐỘ VUÔNG GÓC BIỂU DIỄN TOẠ ĐỘ CỦA N H...

Bài 4: Đường đi ngắn nhất

Trong hệ toạ độ vuông góc biểu diễn toạ độ của N hòn đảo là N ₁ (X 1 ,Y 1 ), N 2 (X 2 ,Y 2 ),..., N n (X n ,Y n ),

các tọa độ là số nguyên 2 byte. Với giả thuyết rằng tất cả các thùng chứa của ca nô chỉ chứa đủ xăng để đi

quãng đường không quá M km. Trên mỗi hòn đảo đều có xăng dự trữ để ca nô có thể nạp đầy các thùng

chứa. Hãy tìm đường đi ngắn nhất có thể của ca nô xuất phát từ đảo N i (X i ,Y i ) đến đảo N j (X j ,Y j )?

Dữ liệu vào trong file văn bản “Bai4.inp” có dạng:

- Dòng đầu chứa số N, M (2<N<=1.000, 1<M<=100.000)

- Dòng thứ hai là số N i và N j

- N dòng tiếp theo là toạ độ lần lượt của N hòn đảo.

(mỗi số cách nhau một dấu cách)

Kết quả cho ra file văn bản “Bai4.out” có dạng:

- Dòng đầu là số hiệu các đảo nằm trên đường đi ngắn nhất có thể từ đảo N i đến N j bỏ qua

những đảo không dừng lại đổ xăng mà nằm trên đường đi.

- Dòng thứ hai là độ dài đường đi làm tròn 3 chữ số sau dấu chấm thập phân.

- Nếu không có đường đi nào thỏa mãn ghi số 0.

Ví dụ:

Bai4.inp Bai4.out Hình minh họa

1 8 4 6

10 5

1 6

9.899

0 0

0 10

10 0

5 5

0 5

7 7

4 4

3 3

0 4

6 0

(Có 50% số test N<=30)