trang chủ / đề bài / icpcwf19_f

Dẫn nước mưa

Đề bài

Mô tả

Porto và thung lũng Douro gần đó nổi tiếng với rượu vang port. Những người yêu rượu từ khắp nơi trên thế giới đến đây để thưởng thức loại rượu ngọt này ngay tại nơi nó được làm ra. Hiệp hội Những người sành rượu Port Quốc tế (ICPC) đang tổ chức các chuyến tham quan những vườn nho ở thượng nguồn sông Douro. Để du khách thấy dễ chịu hơn, ICPC vừa lắp các tấm bạt che nắng phía trên các vườn nho. Các tấm bạt bảo vệ du khách khỏi cháy nắng khi họ dạo giữa những hàng nho và nhâm nhi một ly port lâu năm.

Đáng tiếc là các tấm bạt có một vấn đề nhỏ. Nho cần ánh nắng và nước để lớn. Các tấm bạt cho đủ ánh nắng đi qua, nhưng lại hoàn toàn không thấm nước. Điều đó có nghĩa là nước mưa có thể không tới được các vườn nho bên dưới. Nếu không làm gì, vụ thu hoạch nho năm nay sẽ gặp nguy!

ICPC muốn giải quyết vấn đề bằng cách đục thủng các tấm bạt để nước mưa lọt xuống vườn nho bên dưới. Vì không còn nhiều thời gian trước mùa mưa, ICPC muốn đục ít lỗ nhất có thể mà vẫn đạt được mục tiêu.

Ta xét phiên bản hai chiều của bài toán. Vườn nho cần tưới là một khoảng trên trục x, còn các tấm bạt được mô hình hóa là các đoạn thẳng nằm phía trên trục x. Các tấm bạt đều nằm nghiêng, tức là không song song với trục x hay trục y (xem hình minh họa). Mưa rơi thẳng đứng từ trên cao vô tận. Khi mưa rơi xuống một tấm bạt, nước chảy về phía đầu thấp hơn của tấm bạt và rơi xuống từ đó, trừ khi có một lỗ thủng nằm giữa chỗ mưa rơi xuống và đầu thấp của tấm bạt: khi đó nước sẽ rơi qua lỗ thủng. Sau khi rời khỏi một tấm bạt, nước tiếp tục rơi thẳng đứng. Quá trình này lặp lại cho tới khi nước chạm mặt đất (trục x).

Hình minh họa ví dụ 1. Bên trái: các tấm bạt (đoạn thẳng nghiêng màu đen) và vườn nho (đoạn màu xanh lá ở dưới cùng). Bên phải: một cách tối ưu, đục thủng hai tấm bạt tại các chấm đỏ, khi đó một phần nước mưa (màu xanh dương) bắt đầu từ phía trên vườn nho sẽ chảy tới vườn nho.

Vì lý do pháp lý, bạn phải đảm bảo rằng ít nhất một phần nước mưa tới được vườn nho có xuất phát từ ngay phía trên vườn nho. Điều này nhằm ngăn một vườn nho lấy hết nước mưa từ các vườn nho lân cận (xem ví dụ 2).

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên ℓ, r và n, trong đó (ℓ,r) (0≤ℓ<r≤109) là khoảng biểu diễn vườn nho và n (0≤n≤5·105) là số tấm bạt.

Mỗi dòng trong n dòng tiếp theo mô tả một tấm bạt gồm bốn số nguyên x1,y1,x2,y2, trong đó (x1,y1) là vị trí đầu thấp và (x2,y2) là vị trí đầu cao của tấm bạt (0≤x1,x2≤109, x1≠x2 và 0<y1<y2≤109).

Các hoành độ trong dữ liệu vào (ℓ, r và mọi giá trị x1, x2 của các tấm bạt) đôi một khác nhau. Các tấm bạt không cắt nhau, và không có đầu mút của tấm bạt nào nằm trên một tấm bạt khác.

Dữ liệu ra

In ra số lỗ thủng ít nhất cần đục để một phần nước mưa rơi từ phía trên vườn nho tới được vườn nho.

Ví dụ

Input Output Giải thích
10 20 5
32 50 12 60
30 60 8 70
25 70 0 80
15 30 28 40
5 20 14 25
2 Như hình minh họa: mưa rơi phía trên vườn nho xuống tấm bạt cao nhất, chảy tới đầu thấp x=25, đục thủng hai tấm bạt bên dưới tại x=25, nước rơi xuống tấm bạt từ (15,30) đến (28,40), chảy về đầu thấp x=15 rồi rơi xuống vườn nho (10,20).
2 4 2
3 2 0 3
5 2 1 5
1 Mưa rơi phía trên vườn nho (2,4) đều rơi xuống tấm bạt cao (từ (5,2) đến (1,5)) và chảy ra đầu thấp x=5, ngoài vườn nho. Mưa rơi trong khoảng (0,1) xuống tấm bạt thấp và chảy về x=3 trong vườn nho, nhưng không xuất phát từ phía trên vườn nho nên không được tính. Đục một lỗ trên tấm bạt cao tại hoành độ trong khoảng (2,3): nước rơi xuống tấm bạt thấp và chảy về x=3.

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