Nối dây
Đề bài
Mô tả
Định luật Moore nói rằng số lượng transistor trên một con chip tăng gấp đôi sau mỗi hai năm. Đáng kinh ngạc là định luật này đã đúng trong hơn nửa thế kỷ. Mỗi khi công nghệ hiện tại không còn cho phép tăng thêm, các nhà nghiên cứu lại tìm ra công nghệ chế tạo mới để xếp mạch dày đặc hơn nữa. Trong tương lai gần, điều đó có thể có nghĩa là chip được chế tạo trong không gian ba chiều thay vì hai chiều. Nhưng trong bài này, hai chiều là đủ.
Một vấn đề chung của mọi thiết kế phần cứng hai chiều (chẳng hạn chip, card đồ họa, bo mạch chủ, ...) là việc đặt dây dẫn. Mỗi khi đi dây trên phần cứng, sẽ rất phiền nếu các dây phải cắt nhau. Khi có một chỗ cắt nhau, phải dùng các linh kiện đặc biệt để hai dây điện có thể vượt qua nhau, và điều này làm việc sản xuất tốn kém hơn.
Bài toán như sau: cho một thiết kế phần cứng với một số dây dẫn đã được đặt sẵn (tất cả đều là các đoạn thẳng). Cho thêm điểm đầu và điểm cuối của một dây nối mới cần thêm vào. Hãy xác định số lượng nhỏ nhất các dây có sẵn mà dây mới phải cắt qua để nối điểm đầu với điểm cuối. Dây nối mới không nhất thiết là một đoạn thẳng. Yêu cầu duy nhất là dây mới không được đi qua một điểm mà tại đó hai hay nhiều dây có sẵn gặp nhau hoặc cắt nhau.

Hình: ví dụ thứ nhất (Start là điểm đầu, End là điểm cuối).
Hình trên minh họa ví dụ thứ nhất. Tám dây có sẵn tạo thành năm hình vuông. Điểm đầu và điểm cuối của dây mới lần lượt nằm trong hình vuông bên trái nhất và bên phải nhất. Đường nét đứt màu đen cho thấy nối thẳng sẽ cắt qua bốn dây, còn cách nối tối ưu chỉ cắt qua hai dây (đường cong màu xanh).
Dữ liệu vào
Dòng đầu tiên chứa năm số nguyên , , , , : số dây có sẵn, điểm đầu và điểm cuối cần được nối.
Tiếp theo là dòng, mỗi dòng chứa bốn số nguyên , , , mô tả một dây có sẵn có độ dài khác , nối từ tới .
Dữ liệu ra
In ra số lượng nhỏ nhất các dây phải cắt qua để nối điểm đầu với điểm cuối.
Ràng buộc
- .
- Giá trị tuyệt đối của mọi tọa độ trong dữ liệu vào nhỏ hơn .
- Mỗi cặp dây có nhiều nhất một điểm chung, tức là các dây không chồng lên nhau.
- Điểm đầu và điểm cuối của dây mới không nằm trên dây có sẵn nào (hai điểm này có thể trùng nhau).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 3 3 19 3 0 1 22 1 0 5 22 5 1 0 1 6 5 0 5 6 9 0 9 6 13 0 13 6 17 0 17 6 21 0 21 6 |
2 | Đây là cấu hình trong hình. Đi lên cắt dây , vòng qua phía trên đầu mút các dây dọc rồi đi xuống cắt lại dây : tổng cộng dây. |
| 1 0 5 10 5 0 0 10 10 |
0 | Đi vòng qua một đầu mút của dây duy nhất mà không cắt nó. |
Bình luận