Điểm yếu một nhát cắt
Đề bài
Mô tả
Công ty Phòng chống Đột nhập và Tội phạm (ICPC) chuyên lắp đặt hệ thống phát hiện đột nhập cho nhà ở và doanh nghiệp. Kỳ thi Lập trình Sinh viên Quốc tế (thật trùng hợp, cũng có tên viết tắt là ICPC) đang cân nhắc thuê công ty này bảo vệ căn phòng chứa bộ đề của kỳ Chung kết Thế giới năm sau.
Ban tổ chức muốn ngăn chặn những vụ đột nhập đã từng xảy ra trong các năm trước, chẳng hạn đu dây xuống mặt ngoài tòa nhà để vào qua cửa sổ, bò qua ống thông gió, giả danh Bill Poucher, hay sử dụng một chiếc tàu ngầm tấn công một cách đầy sáng tạo. Vì thế, bộ đề sẽ được cất trong một căn phòng chỉ có một cửa ra vào và không có lối ra nào khác.
ICPC (công ty) đề xuất lắp các cảm biến trên bốn cạnh của cánh cửa, các cặp cảm biến được nối với nhau bằng dây điện. Nếu ai đó mở cửa, mọi cặp cảm biến được nối dây sẽ phát hiện ra và làm chuông báo động kêu.
Tuy nhiên, hệ thống có một lỗi thiết kế: kẻ đột nhập có thể cắt các sợi dây trước khi mở cửa. Để đánh giá độ an toàn của hệ thống, bạn cần xác định số lượng ít nhất các đoạn thẳng (nhát cắt) sao cho mọi sợi dây đều bị ít nhất một nhát cắt cắt qua. Hình dưới đây minh họa hai cách bố trí dây trên cánh cửa (ứng với hai ví dụ) cùng các tập nhát cắt có kích thước nhỏ nhất cắt qua mọi sợi dây.

Hình: (a) bốn sợi dây (xanh) có thể cắt hết bằng một nhát cắt (đỏ); (b) năm sợi dây cần hai nhát cắt.
Cánh cửa là hình chữ nhật với các góc , , và .
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên , và : số sợi dây đã lắp và kích thước của cánh cửa.
Tiếp theo là dòng, mỗi dòng mô tả một sợi dây gồm bốn số nguyên , , , , nghĩa là sợi dây nối từ điểm tới điểm .
Mỗi sợi dây nối hai cạnh khác nhau của cánh cửa. Không sợi dây nào gắn vào một trong bốn góc của cánh cửa. Mọi điểm gắn dây trong dữ liệu vào đều phân biệt.
Dữ liệu ra
In ra một tập nhát cắt (đoạn thẳng) có kích thước nhỏ nhất cắt qua mọi sợi dây. Dòng đầu tiên in số nhát cắt cần dùng. Sau đó in các nhát cắt, mỗi nhát trên một dòng theo dạng cho nhát cắt từ tới (các tọa độ có thể là số thực).
Mỗi nhát cắt phải bắt đầu và kết thúc trên hai cạnh khác nhau của cánh cửa. Đầu mút của nhát cắt không được nằm gần hơn so với bất kỳ điểm gắn dây nào hay bất kỳ góc nào của cánh cửa.
Các nhát cắt có thể in theo thứ tự bất kỳ, hai đầu mút của mỗi nhát cắt cũng có thể in theo thứ tự bất kỳ. Nếu có nhiều tập nhát cắt cùng kích thước nhỏ nhất, in tập nào cũng được.
Ràng buộc
- .
- .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 6 0 1 4 4 0 5 2 0 0 3 3 6 2 6 4 2 |
1 0 4 4 3 |
Hình (a): một nhát cắt từ cạnh trái tới cạnh phải cắt qua cả bốn sợi dây. |
| 5 4 6 0 2 2 0 0 3 2 6 1 6 3 0 1 0 4 4 3 6 4 2 |
2 0 4 4 4.5 0 1 4 1 |
Hình (b): không có nhát cắt đơn nào cắt qua cả năm sợi dây, nên cần hai nhát cắt. |
Bình luận