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

Bài 4: Đường đi ngắn nhấtTrong hệ toạ độ vuông góc biểu diễn toạ độ của N hòn đảo là N

1

(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ọa1 8 4 610 51 69.8990 00 1010 05 50 57 74 43 30 46 0(Có 50% số test N<=30)