ROADS - Khôi phục nông trại
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Sau một trận lũ lụt, một số con đường trong nông trại của anh bị phá hủy, và anh cần gấp rút xây dựng lại chúng, sao cho có thể đi được từ một cánh đồng sang các cánh đồng khác thông qua những con đường không bị phá hủy hoặc mới xây. Có tất cả ~N~ đồng cỏ ~(1 ≤ N ≤ 1000)~ nằm trên các tọa độ ~(X_i, Y_i) (0 ≤ X_i,Y_i ≤ 10^6)~. Có tất cả ~M~ con đường không bị phá hủy ~(1 ≤ M ≤ 1000)~, chúng được mô tả là ~M~ cặp ~(u_k, v_k) (1 ≤ u_k, v_k ≤ N; u_k ≠ v_k)~ tức là đường nối đồng cỏ ~u_k~ và ~v_k~ vẫn tồn tại.
Xác định tổng độ dài nhỏ nhất của các con đường cần xây.
Input
- Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~
- ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~X_i, Y_i~
- ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u_i, v_i~
Output
- Một dòng duy nhất là tổng độ dài các con đường cần xây (in ra hai chữ số sau dấu thập phân và không làm tròn)
Sample
Input #1
4 1
1 1
3 1
2 3
4 3
1 4
Output #1
4.00
Problem source: Kc97ble - Free Contest 17
Bình luận
độ dài này là tính theo độ dài hình học hả ta =))