#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <deque>
using namespace std;

struct pt{
	int x,y;
}points[120];

int ptNum[120];
int ptHeng[120];
int ptList[120][120];

int n,r;

bool compare(const pt &p1, const pt &p2){
	return p1.x<p2.x || (p1.x==p2.x && p1.y<p2.y);
}

int main() {
	int t;
	scanf("%d", &t);
	for(int ii = 0; ii < t; ii++){
		scanf("%d%d", &n, &r);
		for(int j = 0; j < n; j++){
			scanf("%d%d", &points[j].x, &points[j].y);
		}
		sort(points, points+n, compare);
		int hzb = -1;
		int cnt = -1;
		for(int i = 0; i < n; i++){
			if(points[i].x == hzb){
				ptList[cnt][ptNum[cnt]] = points[i].y;
				ptNum[cnt]++;
			}
			else{
				hzb = points[i].x;
				cnt++;
				ptNum[cnt] = 1;
				ptList[cnt][0] = points[i].y;
				ptHeng[cnt] = hzb;
			}
		}
		cnt++;
		int ans = 0;
		for(int i = 0; i < cnt; i++){
			int collect[120], tot = 0;
			int startP = i;
			while(startP < cnt && ptHeng[startP] <= ptHeng[i]+r){
				for(int j = 0; j < ptNum[startP]; j++){
					collect[tot] = ptList[startP][j];
					tot++;
				}
				startP++;
			}
			if(tot <= ans) continue;
			sort(collect, collect+tot);
			int gs = 0;
			int mxGs = 0;
			deque<int> fangye;
			for(int j = 0; j < tot; j++){
				fangye.push_back(collect[j]);
				gs++;
				while(collect[j]-fangye.front() > r){
					fangye.pop_front();
					gs--;
				}
				if(gs > mxGs) mxGs = gs;
			}
			if(mxGs > ans) ans = mxGs;
		}
		printf("%d\n", ans);
	}
	return 0;
}

• Re:优先队列176k0ms1A (1680) KatrineYang 2016-09-23 07:15:09