Subtask 1: ~n \leq 10^2~, ~x_i, y_i, w, h \leq 10^2~. Độ phức tạp ~O(W \times H \times N)~.

Chọn một điểm đã cho làm góc dưới bên trái của hình chữ nhật kết quả. Duyệt tất cả các điểm, kiểm tra và đếm số lượng điểm nằm trong hình chữ nhật. Duyệt mọi hình chữ nhật kết quả để tìm số lượng điểm lớn nhất nằm trong một hình chữ nhật.

Subtask 2: ~n \leq 10^3~, ~x_i, y_i, w, h \leq 10^8~. Độ phức tạp ~O(N \log_2 N)~.

Duyệt các điểm theo thứ tự không giảm của hoành độ ~x~. Duy trì một cửa sổ trượt ~SW_x~ có độ rộng ~w~ để theo dõi các điểm nằm trong cửa sổ này. Với các điểm thuộc ~SW_x~, đếm số điểm có khoảng cách theo tung độ ~y~ không vượt quá ~h~ (nằm trong cửa sổ ~SW_y~).

Cách cài đặt: Dùng hàng đợi ưu tiên (kỹ thuật hai con trỏ) cho ~SW_x~ và multiset cho ~SW_y~. Thuật toán này cũng áp dụng được cho trường hợp tổng quát của bài toán.

Subtask 3: ~n \leq 10^5~, ~x_i, y_i, w, h \leq 10^3~ và một trong các hình chữ nhật kết quả có góc trên bên phải trùng với một điểm đã cho. Độ phức tạp ~O(W \times H + N)~.

Do giá trị tọa độ nhỏ (~10^3~), ta đánh dấu điểm và dùng prefix sum để tính trước. Vì góc trên bên phải của hình chữ nhật kết quả phải là một điểm đã cho, ta dùng nó để xác định các hình chữ nhật hợp lệ.

Duyệt qua ~N~ hình chữ nhật đó theo thứ tự hoành độ không giảm, đếm số điểm và cập nhật giá trị lớn nhất.

Subtask 4: ~n \leq 10^5~, ~x_i, y_i, w, h \leq 10^5~ và 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. Độ phức tạp ~O(N \times \log_2 H)~.

Do giá trị tọa độ lớn (~10^5~) không thể dùng prefix sum nên ta sẽ thay thế bằng cấu trúc dữ liệu, có thể dùng cây Fenwick để thực hiện.

Duyệt qua ~N~ hình chữ nhật có góc trên bên phải là các điểm theo thứ tự không giảm của hoành độ, đếm và cập nhật số lượng điểm lớn nhất bằng cây Fenwick dựa trên tung độ.

Để truy vấn dễ hơn trên cây Fenwick với mỗi điểm ta xác định luôn 3 đỉnh còn lại của hình chữ nhật lấy điểm đó làm góc trên bên phải. Bởi ta cần ~prefix[(x, y)] - prefix[(x - w - 1, y - h - 1)]~. Để dùng cây Fenwick 1D ta hash các đỉnh và tính ~prefix[hash(x, y)] = query(y) - \text{số điểm có tung độ từ } 1 \text{ đến } y~.

Subtask 5: ~n \leq 10^5~, ~x_i, y_i, w, h \leq 10^8~. Độ phức tạp ~O(N \times \log_2 N)~.

Tương tự như thuật toán trong subtask 2, ta cần tối ưu việc xác định các điểm trong ~SW_x~ có tung độ không vượt quá ~h~ và nén dữ liệu:

1. Tìm cấu trúc dữ liệu thích hợp cho việc truy vấn số điểm trong ~SW_x~ có khoảng cách tung độ không vượt quá ~h~.

Trường hợp tổng quát ta có nhận xét rằng, hình chữ nhật kết quả luôn chứa ít nhất một điểm trên biên của nó, nếu không ta có thể dịch hình chữ nhật xuống dưới sao cho không làm mất các điểm bên trong nó cho đến khi có ít nhất một điểm trên biên trên.

Dùng sweep line với hai con trỏ tương ứng với ~SW_x~ như trong subtask 2 và duy trì tung độ các điểm trong ~SW_x~ bằng một cửa sổ cấu trúc dữ liệu có thể trả lời nhanh câu hỏi: Với một điểm trên biên trên có bao nhiêu điểm cách nó một khoảng theo tung độ không quá ~h~ xuống phía dưới.

Trong khi di chuyển cửa sổ trượt ~SW_x~ ta cần thêm hoặc bỏ các điểm, bởi vậy ta cần cập nhật lại các tung độ của các điểm tương ứng với việc thêm bớt. Cấu trúc dữ liệu phù hợp trong trường hợp này là Segment Tree. Và khi thêm hay bớt một điểm có tung độ ~y~ vào cửa sổ trượt ta cần tăng hoặc giảm tất cả các giá trị tung độ trong đoạn ~[y, y + h]~ đi 1. Để thực hiện nhanh điều này ta cần dùng cập nhật lười trên cây phân đoạn ST để tăng tốc độ thực hiện.

2. Nén dữ liệu bởi trong trường hợp này ~x, y \leq 10^8~, quá lớn cho cây phân đoạn.

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> llll;
typedef pair<ld,ld> ldld;

const int N=2e5+5;

vector<int> qu[N],vx,vy;
pii a[N];
int st[4*N],lz[4*N];

void pushdown(int idx,int l,int r)
{
    int temp=lz[idx];
    lz[idx]=0;
    if(l==r) return;
    st[idx<<1]+=temp;
    lz[idx<<1]+=temp;
    st[idx<<1|1]+=temp;
    lz[idx<<1|1]+=temp;
}

void update(int idx,int l,int r,int x,int y,int v)
{
    if(l>y||r<x) return;
    if(l>=x&&r<=y)
    {
        st[idx]+=v;
        lz[idx]+=v;
        return;
    }
    pushdown(idx,l,r);
    int mid=(l+r)>>1;
    update(idx<<1,l,mid,x,y,v);
    update(idx<<1|1,mid+1,r,x,y,v);
    st[idx]=max(st[idx<<1],st[idx<<1|1]);
}

void solve()
{
    int n,w,h;
    cin >> n >> w >> h;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i].fi >> a[i].se;
        vx.push_back(a[i].fi);
        vx.push_back(a[i].fi-w);
        vy.push_back(a[i].se);
        vy.push_back(a[i].se-h);
    }
    sort(vx.begin(),vx.end());
    sort(vy.begin(),vy.end());
    vx.erase(unique(vx.begin(),vx.end()),vx.end());
    vy.erase(unique(vy.begin(),vy.end()),vy.end());
    for(int i=1;i<=n;i++) qu[lower_bound(vx.begin(),vx.end(),a[i].fi)-vx.begin()].push_back(a[i].se);
    n=(int)vy.size();
    int ans=0;
    for(int i=0,j=0;i<(int)vx.size();i++)
    {
        while(vx[i]-vx[j]>w)
        {
            for(int k=0;k<(int)qu[j].size();k++)
            {
                int v=qu[j][k];
                int l=lower_bound(vy.begin(),vy.end(),v-h)-vy.begin()+1;
                int r=lower_bound(vy.begin(),vy.end(),v)-vy.begin()+1;
                update(1,1,n,l,r,-1);
            }
            j++;
        }
        for(int j=0;j<(int)qu[i].size();j++)
        {
            int v=qu[i][j];
            int l=lower_bound(vy.begin(),vy.end(),v-h)-vy.begin()+1;
            int r=lower_bound(vy.begin(),vy.end(),v)-vy.begin()+1;
            update(1,1,n,l,r,1);
        }
        ans=max(ans,st[1]);
    }
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen("rectpoints.inp","r"))
    {
        freopen("rectpoints.inp","r",stdin);
        freopen("rectpoints.out","w",stdout);
    }
    int t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}