4110654_ac_0ms_224k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n, r;
struct node
{
	int x, y;
}p[100];

typedef vector <node> TYPE;

bool cmpx(node a, node b)
{
	return a.x < b.x;
}

int ans;

bool cmpy(node a, node b)
{
	return a.y < b.y;
}

void solve()
{
	int i, j, k;
	TYPE all;

	for (i = 0; i < n; i++)
	{
		if (n - i <= ans)
			return ;
		all.clear();
		for (j = i; j < n; j++)
		{
			if (p[j].x - p[i].x <= r)
			{
				all.push_back(p[j]);
			}
			else
				break;
		}
		if (all.size() <= ans)
			continue;
		sort(all.begin(), all.end(), cmpy);
		for (j = 0; j + ans < all.size(); j++)
		{
			int tmp = 0;
			for (k = j; k < all.size(); k++)
			{
				if (all[k].y - all[j].y <= r)
					tmp++;
				else
					break;
			}
			if (tmp > ans)
				ans = tmp;
		}
	}
}

int main()
{
	int t;

	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &n, &r);
		for (int i = 0; i < n; i++)
		{
			scanf("%d%d", &p[i].x, &p[i].y);
		}
		sort(p, p + n, cmpx);
		ans = 0;
		solve();
		printf("%d\n", ans);
	}
	return 0;
}