Most Points in a Fixed Rectangle
Autumn Tournament (2020)
Submission name: rectpoints.cpp
Problem summary
Place an axis-parallel rectangle of width w and height h to cover as many given points as possible. Boundary points count, and coincident input points remain distinct. The rectangle may be translated but not rotated.
Input
N w h, then N pairs x y.
Output
The maximum covered point count.
Constraints
1≤N≤100000; 1≤x,y,w,h≤100000000.
Worked example
Original statement sample.
Input
6 2 3 1 1 3 1 2 2 3 3 5 3 3 5
Output
4
Solution analysis
- Sort the points by x. For each rightmost x-coordinate, keep all processed points with x at least right−w. The two-pointer window contains exactly the points that could fit horizontally into that width; a point on either boundary is retained.
- The remaining question is the best vertical placement. An optimal bottom edge can be moved up to the smallest y-coordinate of a covered point. Compress all input y-coordinates as candidate bottom edges. A point at y contributes one to each candidate bottom in the closed interval [y−h,y].
- Adding or removing a point is therefore a range increment or decrement. A lazy segment tree stores the maximum count over all bottom candidates. Update the tree as the horizontal window changes and maximize its root value. In the sample, x from1to3 and y from0to3 cover four points; y=3 lies on the top boundary and counts.
Why it works
For any optimum, move its right edge left until it reaches a covered point and its bottom edge up until it reaches a covered point; neither move loses a point. The sweep considers that horizontal endpoint, and the compressed candidate set contains that bottom endpoint. Range updates count exactly the active points covering each vertical placement, so the tree maximum finds the optimum.
Watch out. Remove a point only when its horizontal distance exceeds w, not when it equals w. Use closed vertical ranges. Do not assume one input point must be a corner: the optimum’s horizontal and vertical anchors may be different points. Count duplicate points separately.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct Point{
int x;
int y;
};
class SegmentTree{
int n;
vector<int>maximum;
vector<int>lazy;
void add(int node,int left,int right,int from,int to,int value){
if(from<=left&&right<=to){
maximum[node]+=value;
lazy[node]+=value;
return;
}
int middle=(left+right)/2;
if(from<=middle){
add(node*2,left,middle,from,to,value);
}
if(to>middle){
add(node*2+1,middle+1,right,from,to,value);
}
maximum[node]=lazy[node]+max(maximum[node*2],maximum[node*2+1]);
}
public:
explicit SegmentTree(int size):n(size),maximum(4*size),lazy(4*size){
}
void add(int left,int right,int value){
if(left<=right){
add(1,0,n-1,left,right,value);
}
}
int best()const{
return maximum[1];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,width,height;
cin>>n>>width>>height;
vector<Point>points(n);
vector<int>bottoms;
for(Point&point:points){
cin>>point.x>>point.y;
bottoms.push_back(point.y);
}
sort(points.begin(),points.end(),[](Point a,Point b){
return a.x<b.x;
});
sort(bottoms.begin(),bottoms.end());
bottoms.erase(unique(bottoms.begin(),bottoms.end()),bottoms.end());
SegmentTree tree(static_cast<int>(bottoms.size()));
auto update=[&](const Point&point,int value){
int left=lower_bound(bottoms.begin(),bottoms.end(),point.y-height)-bottoms.begin();
int right=upper_bound(bottoms.begin(),bottoms.end(),point.y)-bottoms.begin()-1;
tree.add(left,right,value);
};
int left=0;
int answer=0;
for(int right=0;right<n;right++){
update(points[right],1);
while(points[right].x-points[left].x>width){
update(points[left],-1);
left++;
}
// The root is the best vertical placement for this horizontal window.
answer=max(answer,tree.best());
}
cout<<answer<<'\n';
}