【题意】给了n个点，求一个正方形能围住的最大点数，同样正方形平行于坐标轴。

【解题方法1】线段树+扫描线。AC时间：30ms。


//
//Created by just_sort 2016/12/3
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define MP(x,y) make_pair(x,y)
const int maxn = 10010;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head

LL L, R, n, r;
LL b[3005];
struct seg{
    LL x, y, v;
    seg(){}
    seg(LL x, LL y, LL v):x(x), y(y), v(v){}
}s[3005];
struct node{
    int l, r;
    LL num, lazy;
}T[30005];

bool cmp1(const seg &a, const seg &b)
{
    if(a.x == b.x) return a.v > b.v;
    return a.x < b.x;
}

bool cmp2(const seg &a, const seg &b)
{
    return a.y < b.y;
}

void pushup(int rt)
{
    T[rt].num = max(T[rt*2].num, T[rt*2+1].num);
}

void pushdown(int rt)
{
    if(T[rt].lazy != 0)
    {
        T[rt*2].lazy += T[rt].lazy;
        T[rt*2+1].lazy += T[rt].lazy;
        T[rt*2].num += T[rt].lazy;
        T[rt*2+1].num += T[rt].lazy;
        T[rt].lazy = 0;
    }
}

void Build(int l, int r, int rt)
{
    T[rt].l = l, T[rt].r = r, T[rt].num = T[rt].lazy = 0;
    if(l == r) return ;
    int mid = (l + r) / 2;
    Build(l, mid, rt*2);
    Build(mid+1, r, rt*2+1);
}

void update(int v, int rt)
{
    if(L <= T[rt].l && T[rt].r <= R){
        T[rt].lazy += v;
        T[rt].num += v;
        return ;
    }
    pushdown(rt);
    int mid = (T[rt].l + T[rt].r) / 2;
    if(L <= mid) update(v, rt*2);
    if(mid < R) update(v, rt*2+1);
    pushup(rt);
}

int main()
{
    while(scanf("%I64d%I64d",&n,&r)!=EOF)
    {
        memset(b, 0, sizeof(b));
        for(int i = 1; i <= n; i++){
            LL x, y;
            scanf("%I64d%I64d",&x, &y);
            s[3*i - 2] = seg(x, y, 1);
            s[3*i - 1] = seg(x+r, y, -1);
            s[3*i] = seg(x, y+r, 0);
        }
        sort(s+1, s+3*n+1, cmp2);
        for(int i = 1; i <= 3*n; i++) b[i] = s[i].y;
        int sz = unique(b+1, b+3*n+1) - b - 1;
        sort(s+1, s+3*n+1, cmp1);
        Build(1, sz, 1);
        LL ans = 0;
        for(int i = 1; i <= 3*n; i++){
            if(s[i].v == 0) continue;
            L = lower_bound(b + 1, b + sz + 1, s[i].y) - b;
            R = lower_bound(b + 1, b + sz + 1, s[i].y + r) - b;
            update(s[i].v, 1);
            ans = max(ans, T[1].num);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

【解题方法2】 双扫描线+暴力  AC时间：780ms

【具体步骤】首先将所有点按横坐标大小排序，然后以a[i].x为第一条竖扫描线，a[i].x+r为第二条竖扫描线，在存下在这个区间内的点的y坐标b[i]。将b数组从小到大排序，再以b[i]为第一条横扫描线，b[i]+r为第二条横扫描线，如果寻找到满足的坐标，curans++。最后找出最大的nexans，记得下一次操作curans前重新赋值!

【AC代码】

//
//Created by just_sort 2016/12/3
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define MP(x,y) make_pair(x,y)
const int maxn = 10010;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head

struct node{
    int x, y;
    node(){}
    node(int x, int y) : x(x), y(y) {}
    bool operator<(const node &rhs) const{
        if(x == rhs.x) return y < rhs.y;
        return x < rhs.x;
    }
}a[1010];
int b[1010];
int main()
{
    int n, r;
    while(scanf("%d%d",&n,&r) != EOF)
    {
        for(int i = 1; i <= n; i++) scanf("%d%d",&a[i].x,&a[i].y);
        sort(a+1, a+n+1);
        int curans = 0, nexans = 0;
        for(int i = 1; i <= n; i++){
            int xUp = a[i].x + r;
            int k = 0;
            for(int j = i; j <= n; j++){
                if(a[j].x <= xUp){
                    b[++k] = a[j].y;
                }
            }
            sort(b+1, b+k+1);
            for(int j = 1; j <= k; j++){
                int yUp = b[j] + r;
                curans = 0;
                for(int l = j; l <= k; l++){
                    if(b[l] <= yUp){
                        curans++;
                    }
                }
                nexans = max(nexans, curans);
            }
        }
        printf("%d\n",nexans);
    }
    return 0;
}