trang chủ / đề bài / icpcwf18_h

Đ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 (0,0), (w,0), (w,h) và (0,h).

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên n, w và h: số sợi dây đã lắp và kích thước của cánh cửa.

Tiếp theo là n dòng, mỗi dòng mô tả một sợi dây gồm bốn số nguyên x1, y1, x2, y2, nghĩa là sợi dây nối từ điểm (x1,y1) tới điểm (x2,y2).

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 x1 y1 x2 y2 cho nhát cắt từ (x1,y1) tới (x2,y2) (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 10−6 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

  • 1≤n≤106.
  • 1≤w,h≤108.
  • 0≤x1,x2≤w, 0≤y1,y2≤h.

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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0