Hệ
thống đường cao tốc hiện tại ở thành phố A mới đảm bảo đi lại giữa một số nút
giao thông trọng điểm và còn nhiều nút giao thông trọng điểm khác vẫn chưa có
đường cao tốc đi qua nó. Để giải tỏa tình trạng ách tắc giao thông của thành phố,
chính quyền thành phố quyết định phát triển hệ thống đường cao tốc của thành
phố sao cho có thể đi lại giữa hai nút giao thông trọng điểm bất kỳ. Có N nút
giao thông trọng điểm được đánh số từ 1 đến N. Nút giao thông i được cho bởi tọa
độ (xi,yi) trong hệ thống tọa độ Đềcác. Mỗi tuyến đường chính là khoảng cách
giữa hai điểm tương ứng với hai nút giao thông trọng điểm. Tất cả các tuyến đường
cao tốc là hai chiều. Các tuyến đường có thể cắt nhau nhưng người sử dụng
phương tiện giao thông chỉ được đổi tuyến đi ở các nút giao thông là đầu mút của
các tuyến đường. Chính quyền thành phố muốn tìm cách xây dựng bổ sung một số
tuyến đường cao tốc nối các nút giao thông trọng điểm với chi phí nhỏ nhất đảm
bảo sự đi lại giữa mọi nút giao thông trọng điểm. Chi phí bổ sung như là tổng độ
dài của các tuyến đường cần xây dựng
Dữ liệu vào: từ file văn bản
HIGHWAY.INP
+
Dòng đầu tiên chứa số N (N≤750)
+
Dòng thứ i trong số N dòng tiếp theo chứa tọa độ (xi,yi) của nút giao thông trọng
điểm i
+
Dòng tiếp theo chứa M là số tuyến đường cao tốc hiện có (0≤M≤1000)
+
Dòng thứ j trong số M dòng tiếp theo chứa hai số nguyên dương u, v cho biết đã
có tuyến đường cao tốc nối từ nút giao thông u đến nút v. (1<=u,v<=n)
Dữ liệu ra: ghi vào file
HIGHWAY.OUT
+
Dòng đầu tiên ghi số K cho biết số lượng các tuyến đường cần xây dựng
+
K dòng tiếp theo mỗi dòng ghi hai số u và v cho biết tuyến đường giữa
hai thành phố u và v cần xây dựng
Ví dụ
|
|
HIGHWAY.INP
|
HIGHWAY.OUT
|
9
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
4
1 3
9 7
1 2
2 3
|
5
1 6
3 7
3 8
4 9
5 7
|
