题意： 知道了 n 个人的坐标和一个边长为R的正方形，问正方形内最多可以包含多少人。
分析：离散化坐标，将y坐标映射到区间上，按x坐标从小到达扫描。
#include#include #include using namespace std;#define maxn 10005long long max(long long a, long long b){ return a>b?a:b;}struct seg{ long long x, y, val;}s[maxn*2];int add[maxn<<3];int val[maxn<<3];long long Y[maxn*2];bool cmp(seg a, seg b){ if(a.x != b.x) return a.x < b.x; return a.val < b.val;}void update(long long L, long long R, long long va, long long l, long long r, long long rt){ if (L <= l && r <= R) { add[rt] += va; val[rt] += va; return; } if (add[rt]) { add[rt<<1] += add[rt]; add[rt<<1|1] += add[rt]; val[rt<<1] += add[rt]; val[rt<<1|1] += add[rt]; add[rt] = 0; } long long m = (l + r)>>1; if (L <= m) update(L, R, va, l, m, rt<<1); if (R > m) update(L, R, va, m+1, r, rt<<1|1); val[rt] = max(val[rt<<1], val[rt<<1|1]);}long long b_search(long long key, long long n){ long long m, l = 1, r = n; while (l <= r) { m = (l+r)>>1; if (Y[m] == key) return m; else if (Y[m] > key) r = m-1; else l = m+1; } return -1;}int main(){ long long i, m, l, r, res; long long n, R; while (scanf("%I64d %I64d",&n, &R) != EOF) { for (i=1; i<=n; i++) { scanf("%I64d %I64d",&s[i].x, &s[i].y); s[i].val = 1; s[i+n] = s[i]; s[i+n].x = s[i].x + R +1; s[i+n].val = -1; Y[i] = s[i].y; Y[i+n] = s[i].y+R; } sort(Y+1, Y+2*n+1); sort(s+1, s+2*n+1, cmp); m = 1; for (i=1; i<=2*n; i++) if (Y[i] != Y[m]) Y[++m] = Y[i]; memset(add, 0, sizeof(add)); memset(val,0,sizeof(val)); res = 0; for (i=1; i<=2*n; i++) { l = b_search(s[i].y, m); r = b_search(s[i].y+R, m); update(l, r, s[i].val, 1, m, 1); res = max(res,val[1]); } printf("%I64d\n",res); } return 0;}