#688. GASISLAND - Hệ thống đảo cung cấp xăng

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài
Đưa lên bởi: Chùm CUỐI

Đề bài

Vùng Hạ Long có N\ (2 ≤ N ≤ 1000) hòn đảo được đánh số từ 1 đến N . Tọa độ hòn đảo thứ i trên mặt phẳng tọa độ được cho bởi cặp số (x_i,y_i) . Trên mỗi đảo có bể chứa xăng có khả năng cung cấp đầy các thiết bị chứa xăng của ca nô. Biết rằng các thiết bị chứa xăng của ca nô không thể chứa đủ số xăng đi hết M km.

Hãy tìm một hành trình cho ca nô đi từ một đảo U đến đảo V\ (0 < U, V ≤ N) mà số lần ghé vào các đảo để lấy xăng là nhỏ nhất.

Dữ liệu vào:

  • Dòng đầu ghi 4 số nguyên dương N, M, U, V ;
  • Các dòng tiếp theo, dòng i chứa hai số nguyên x_i y_i\ (|x_i|, |y_i| ≤ 1000) là tọa độ đảo thứ i .
Dữ liệu ra:
  • Nếu có đường đi thì dòng đầu tiên ghi số đảo ghé vào lấy xăng (trừ U V ), dòng thứ hai ghi số hiệu các đảo theo thứ tự của hành trình. Nếu không có đường đi thì ghi -1 .

Ví dụ:

Dữ liệu vào:
12 10 1 12
0 0
8 0
8 6
0 8
10 4
15 4
20 8
20 0
25 8
25 4
25 0
30 14
Dữ liệu ra:
4
2 6 7 9