3838150_ac_188ms_212k.cpp

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

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

using namespace std;

int c, n;
struct point
{
	int x, y;
}p[500], t[500];

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

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

int can(int l)
{
	int i, x, j, d;
	
	for (i = 0; i < n; i++)
	{
		x = p[i].x + l;
		d = 0;
		for (j = i; j < n; j++)
		{
			if (p[j].x >= x)
				break;
			t[d++] = p[j];
		}
		sort(t, t + d, cmpy);
		for (j = c - 1; j < d; j++)
		{
			if (t[j].y - t[j - c + 1].y < l)
			{
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	int i;

	scanf("%d%d", &c, &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d%d", &p[i].x, &p[i].y);
	}
	sort(p, p + n, cmpx);
	int min, max, mid;
	min = 1;max = 10000;
	while (min < max)
	{
		mid = (min + max) >> 1;
		if (can(mid))
			max = mid;
		else
			min = mid + 1;
	}
	printf("%d\n", min);
	return 0;
}