Cover the Most Points with a Fixed Rectangle
Autumn Tournament (2020)
Submission name: rectpoints.cpp
Problem summary
Place an axis-aligned rectangle of fixed width w and height h to cover as many of the given points as possible. Points on its boundary count, and coincident input points count separately.
Input
N w h, followed by N coordinate pairs x y.
Output
The maximum number of covered points.
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 points by x. For each rightmost x-coordinate, retain exactly the points whose x lies in [x−w,x]. A two-pointer sweep inserts each point once and removes it once. Inclusive boundaries matter: remove a point only when its x is strictly smaller than x−w.
- For a retained point (x,y), a rectangle with top side at height Y covers it precisely when y≤Y≤y+h. Thus that point contributes +1 to the interval [y,y+h] of possible top-side positions. We need the maximum overlap of all these intervals.
- An optimal top side can be shifted down until it meets a retained point, so only input y-coordinates need be queried. Compress all y values. A lazy segment tree supports adding1 or−1 to the compressed interval [y,y+h] and reporting the largest count over all top-side choices.
- In the sample, after processing x=3 the active points include (1,1),(3,1),(2,2),(3,3),(3,5). At top side Y=3, the height3 rectangle covers the first four points. Its x-range is[1,3], and its y-range is[0,3], giving answer4.
Why it works
Any feasible rectangle can be shifted horizontally until its right boundary meets a covered point without losing points. That right coordinate is examined by the sweep. For that active x-window, every point contributes exactly to the top-side positions covering it, and the segment-tree maximum is the best vertical placement. Maximizing over all sweep positions therefore finds an optimum.
Watch out. Do not require the top-right corner itself to be an input point. Count duplicates independently and keep equality at both boundaries. Removing at x−w rather than strictly before it loses boundary points.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Any feasible rectangle can be shifted horizontally until its right boundary meets a
// covered point without losing points. That right coordinate is examined by the sweep.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct Point{
int x;
int y;
};
struct SegmentTree{
int size;
vector<int>maximum;
vector<int>lazy;
SegmentTree(int n):size(n),maximum(4*n),lazy(4*n){
}
void add(int node,int left,int right,int from,int to,int value){
if(from>right||to<left){
return;
}
if(from<=left&&right<=to){
maximum[node]+=value;
lazy[node]+=value;
return;
}
int middle=(left+right)/2;
add(node*2,left,middle,from,to,value);
add(node*2+1,middle+1,right,from,to,value);
maximum[node]=lazy[node]+max(maximum[node*2],maximum[node*2+1]);
}
void add(int left,int right,int value){
add(1,0,size-1,left,right,value);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int width;
int height;
cin>>n>>width>>height;
vector<Point>points(n);
vector<int>coordinates;
for(Point&point:points){
cin>>point.x>>point.y;
coordinates.push_back(point.y);
}
sort(points.begin(),points.end(),[](Point a,Point b){
return a.x<b.x;
});
sort(coordinates.begin(),coordinates.end());
coordinates.erase(unique(coordinates.begin(),coordinates.end()),coordinates.end());
SegmentTree tree(static_cast<int>(coordinates.size()));
auto update=[&](Point point,int value){
int left=lower_bound(coordinates.begin(),coordinates.end(),point.y)-coordinates.begin();
int right=
upper_bound(coordinates.begin(),coordinates.end(),point.y+height)-coordinates.begin()-1;
tree.add(left,right,value);
};
int first=0;
int answer=0;
for(int last=0;last<n;last++){
update(points[last],1);
while(points[first].x<points[last].x-width){
update(points[first],-1);
first++;
}
answer=max(answer,tree.maximum[1]);
}
cout<<answer<<'\n';
}