Chọn ĐTQG Quảng Trị 2024 - Phủ điểm

Xem dạng PDF

Gửi bài giải

Điểm: 45,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

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

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

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 cùng 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, chiều cao của tờ giấy và mảnh giấy phủ được 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òng đầu chứa ba số nguyên ~n, w, h~ ~(1 \le n \le 10^5, 1 \le w, h \le 10^8)~;

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

Các số trên một dòng cách nhau dấu cách.

Output

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 Ràng buộc
1 ~10\%~ ~n \le 10~ và ~x_i, y_i, w, h \le 10^2~
2 ~25\%~ ~n \le 10^3~ và ~x_i, y_i, w, h \le 10^8~
3 ~15\%~ ~n \le 10^5~ và ~x_i, y_i, w, h \le 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 \le 10^5~ và ~x_i, y_i, w, h \le 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.