Choosing Points 2
Time limit2sMemory limit128 MB
Given up to 100 points and a fixed rectangle width A and height B, find the placement that covers the maximum number of points, including boundary points.
- Level
Medium6 of 10
- Topics
- Array, Sorting, Two pointers
- Solved
- No attempts yet
Problem
You are given N distinct points on a two-dimensional plane. Place one rectangle with horizontal side length A and vertical side length B so that it contains as many of the given points as possible.
Points on the boundary of the rectangle are also considered to be inside it. Find the maximum possible number of contained points.
Input
The first line contains three integers N, A, and B. Each of the next N lines contains the x and y coordinates of one point.
1 <= N <= 100 and 1 <= A, B <= 2,000,000,000. Every coordinate is an integer whose absolute value is at most 2,000,000,000, and no two points have the same position.
Output
Print the maximum number of points that can be contained in the rectangle.