hdu4001

参考博客http://www.cppblog.com/aswmtjdsj/archive/2011/09/04/155049.aspx

维护4根双扫描线，左右和上下。暴力枚举，复杂度O(n^2).

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1001;
struct Point{
	int x, y;
};
int n, R;
Point vx[MAXN], vy[MAXN];
bool cmpx(Point a, Point b){
	return a.x < b.x;
}
bool cmpy(Point a, Point b){
	return a.y < b.y;
}
int getMAX(){
	int l, r, u,i,j,t=0;;
	int ans = 0;
	for (i = 0; i < n; i++){
		l = vx[i].x;     //左边线
		while (t < n&&vx[t].x - l <= R)t++;
		t--;
		r = vx[t].x;
		int s = 0,temp=0;
		for (j = 0; j < n; j++){
			u = vy[j].y;
			while (s < n&&vy[s].y - u <= R){
				if (vy[s].x <= r&&vy[s].x>=l)
				    temp++;
				s++;
			}
			ans = max(ans, temp);
			//为下一次做准备
			if (vy[j].x <= r&&vy[j].x >= l)
				temp--;
		}
	}
	return ans;
}
int main(){
	while (~scanf("%d%d", &n, &R)){
		for (int i = 0; i < n; i++){
			scanf("%d%d", &vx[i].x, &vx[i].y);
			vy[i] = vx[i];
		}
		sort(vx, vx + n, cmpx);
		sort(vy, vy + n, cmpy);
		int ans = getMAX();
		printf("%d
", ans);
	}
	return 0;
}