Chọn Đội tuyển HSGQG Quảng Trị 2024 - RECTPOINTS

Xem dạng PDF

Gửi bài giải

Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: rectpoints.inp
Output: rectpoints.out

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong thời gian chờ vào tiết học, An và Lạc cùng nhau chơi một trò chơi đơn giản. An lấy một tờ giấy và học sinh hình chữ nhật kẻ ô vuông có chiều rộng ~W~, chiều cao ~H~ và vẽ một số điểm lên tờ giấy đó. Có thể xem góc dưới bên trái của tờ giấy có tọa độ ~(0, 0)~ và góc trên bên phải có tọa độ ~(W, H)~. Các điểm có thể vẽ trùng nhau nhưng được tính như các điểm phân biệt. Lạc lấy ra một mảnh giấy hình chữ nhật có chiều rộng ~w~, chiều cao ~h~ và hai bạn tìm cách đặt mảnh giấy này lên tờ giấy sao cho các cạnh của mảnh giấy song song với các biên của tờ giấy đã vẽ các điểm, chiều rộng và chiều cao mảnh giấy tương ứng với chiều rộng và chiều cao của tờ giấy và mảnh giấy phủ nhiều điểm nhất có thể. Các điểm nằm trên biên của mảnh giấy cũng được xem là bị phủ.

An, Lạc đã vào lớp. Bạn hãy tiếp tục trò chơi khi tờ giấy và mảnh giấy có kích thước lớn hơn.

Yêu cầu: Cho ~n~ điểm và kích thước ~w, h~ của mảnh giấy, hãy tìm số điểm lớn nhất bị phủ bởi mảnh giấy hình chữ nhật đó.

Input

Dữ liệu vào từ tệp văn bản RECTPOINTS.INP gồm:

  • Dòng đầu chứa ba số nguyên ~n, w, h~ (~1 \leq n \leq 10^5, 1 \leq w, h \leq 10^8~);

  • ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i, y_i~ là tọa độ của điểm thứ ~i~ được vẽ trên tờ giấy (~1 \leq x_i, y_i \leq 10^8~).

Các số trên mỗi dòng được ghi cách nhau dấu cách.

Output

Kết quả ghi ra tệp văn bản RECTPOINTS.OUT gồm một dòng ghi một số là số lượng điểm lớn nhất bị phủ bởi mảnh giấy hình chữ nhật.

Scoring

Subtask Điểm Giới hạn
1 ~10\%~ ~n \leq 10^2~ và ~x_i, y_i, w, h \leq 10^2~
2 ~25\%~ ~n \leq 10^3~ và ~x_i, y_i, w, h \leq 10^8~
3 ~15\%~ ~n \leq 10^5~, ~x_i, y_i, w, h \leq 10^3~, một trong các hình chữ nhật kết quả có góc trên bên phải là một trong các điểm đã cho
4 ~15\%~ ~n \leq 10^5~, ~x_i, y_i, w, h \leq 10^5~, một trong các hình chữ nhật kết quả có góc trên bên phải là một trong các điểm đã cho
5 ~35\%~ Không có ràng buộc gì thêm

Sample Input 1

6 2 3
1 1
3 1
2 2
3 3
5 3
3 5

Sample Output 1

4

Sample Input 2

10 8 8
8 9
20 14
3 9
7 8
3 4
7 8
10 19
6 11
5 10
8 2

Sample Output 2

7

Bình luận

Hãy đọc nội quy trước khi bình luận.


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