Most Points in an Anchored Rectangle
National Olympiad — Regional round (2015 season)
Submission name: rect.cpp
Problem summary
Among axis-aligned a-by-b rectangles whose upper-left corner is one of the given points, find the largest number of points covered, including boundary points.
Input
n a b, followed by n distinct integer-coordinate points.
Output
The maximum covered-point count.
Constraints
0 < n < 100000; 0 < a,b < 50; 0 < x < 1000000; 0 < y < 50; points are distinct.
Worked example
Input and output for the worked example discussed below.
Input
6 3 2 13 1 17 8 1 1 10 2 13 2 14 1
Output
3
Solution analysis
- A rectangle anchored at (x,y) covers x-coordinates [x,x+a] and y-coordinates [y−b,y]. The upper-left requirement fixes its vertical interval as well as its horizontal start; an arbitrary optimal rectangle is not necessarily legal.
- Sort points by x. As anchor x increases, maintain exactly the points in the inclusive horizontal window [x,x+a], using two monotone pointers. Store their counts for each y level, of which there are only 49.
- For each original point used as an anchor, sum the active counts at y levels max(1,y−b)…y. This checks at most 50 levels per point. Process equal-x anchors without removing other points at that same x.
- In the sample, anchoring at (13,2) covers (13,1),(13,2),(14,1), giving 3. A point on x+a or y−b still counts because the rectangle’s contour is included.
Why it works
At each anchor the pointer invariant retains exactly the points within its horizontal range. Summing the allowed y-level counts therefore counts exactly the points inside or on that rectangle. Every legal anchor is one of the input points and is tested, so the maximum is optimal.
Watch out. Use y−b…y because the anchor is upper-left in Cartesian coordinates. Keep both interval endpoints inclusive. Do not discard earlier equal-x points while processing another anchor at the same x.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
int n;
int a;
int b;
cin>>n>>a>>b;
vector<pair<int,int>>points(n);
for(auto&point:points){
cin>>point.first>>point.second;
}
sort(points.begin(),points.end());
int frequency[50]={};
int left=0;
int right=0;
int answer=0;
for(const auto&anchor:points){
while(right<n&&points[right].first<=anchor.first+a){
frequency[points[right].second]++;
right++;
}
while(left<n&&points[left].first<anchor.first){
frequency[points[left].second]--;
left++;
}
int covered=0;
// The anchor is the upper-left corner, so covered y values lie below it.
for(int y=max(1,anchor.second-b);y<=anchor.second;y++){
covered+=frequency[y];
}
answer=max(answer,covered);
}
cout<<answer<<'\n';
}