GOLD - Đảo giấu vàng
Giới hạn- Thời gian: 0.095s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
1 nhà thám hiểm nọ vừa phát hiện ra một bản đồ kho báu . Trên bản đồ miêu tả 1 hòn đảo
nằm ở nam Thái Bình Dương . Trên hòn đảo có N vị trí có kho báu là các mỏ vàng . Để được phép khai thác nhà thám hiểm quyết định dốc hết tiền của ra mua 1 mảnh đất và khai thác các mỏ vàng trên đó . Tuy nhiên Nhà thám hiểm cũng không giàu có gì lắm nên chỉ có thể mua được 1 miếng đất hình chữ nhật có kích thước tối đa là S * W và theo yêu cầu của Chúa Đảo thì miếng đất phải song song với 2 trục Ox và Oy để không làm mất mỹ quan của hòn đảo ( các mỏ vàng nằm trên đường biên của miếng đất cũng sẽ được quyền khai thác ) . Bạn hãy lập trình giúp Nhà thám hiểm tính xem ông ta có thể chiếm được nhiều nhất là bao nhiêu mỏ vàng .
Lưu ý : Bài này nếu không cẩn thận sẽ rất dễ bị ngộ nhận . Vì vậy nên phải đặc biệt chú ý. Là 1 bài khó vì thế nên sau một thời gian sẽ để cho các bạn có thể xem lời giải và download test .
Download test và solution tại
đây
.
Input
Dòng 1 : 2 số nguyên dương S W ( 1 ≤ S , W ≤ 10000 ). S là độ dài cạnh song song với trục Ox .
W là độ dài cạnh song song với trục Oy .
Dòng 2 : số nguyên dương N ( 1 ≤ N ≤ 15000 ) .
N dòng tiếp theo , dòng thứ i mô tả vị trí của mỏ vàng thứ i là 2 số nguyên xi và yi .
( -30000 ≤ xi , yi ≤ 30000 ) .
Output
Gồm 1 dòng duy nhất ghi ra số lượng nhiều nhất mỏ vàng mà Nhà thám hiểm có thể có được .
Example
Input: 1 2 12 0 0 1 1 2 2 3 3 4 5 5 5 4 2 1 4 0 5 5 0 2 3 3 2 Output: 4
- Người up: hard7771988
- Nguồn bài: Polish Olympiad in Informatics