Cho một lưới ô vuông trên mặt phẳng với
hệ tọa độ trực chuẩn có một cạnh nằm trên tia Ox và một cạnh nằm trên tia Oy.
Trên lưới người ta đặt n đèn ở các điểm có tọa độ nguyên và
điền số 0 vào tất cả các ô của lưới . Hai bóng đèn được nối với nhau bằng dây dẫn,
dây dẫn luôn là một đoạn thẳng nối hai đèn và tất cả các ô trong các ô vuông có
điểm trong chung với dây dẫn được tăng lên một đơn vị.
Hệ thống đèn chỉ hoạt động nếu hai bóng
đèn bất kỳ luôn được nối với nhau (trực tiếp hoặc thông qua một số bóng đèn
trung gian)
Yêu cầu: Nối các dây dẫn
cho hệ thống hoạt động sao cho khi hoàn thành, tổng các số ghi trên các ô của
lưới là nhỏ nhất có thể.
Dữ liệu: Vào từ tệp văn bản
WIRES.INP
+ Dòng đầu chứa số nguyên dương n
≤ 1000
+ n dòng tiếp theo, mỗi dòng chứa hoành
độ và tung độ một đèn, tọa độ là số tự nhiên có giá rị không quá 109.
Các đèn luôn đảm bảo nằm trong lưới.
Kết quả: ghi ra tệp văn bản
WIRES.OUT
+ Dòng 1 ghi tổng các số trên các ô
vuông của lưới theo phương án tìm được.
+ Các dòng tiếp
theo, mỗi dòng ghi 2 chỉ số của 2 đèn được nối với nhau bằng dây dẫn
Ví dụ:
WIRES.INP
|
WIRES.OUT
|
5
0 1
1 4
2 2
3 0
4 3
|
8
1 3
2 3
4 3
5 3
|
