3838088_ac_250ms_236k.cpp

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

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

using namespace std;

int c, n;
struct point
{
	int x, y;
};

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

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

vector <point> p, tp;

bool can(int length)
{
	int i, x, j;
	
	for (i = 0; i < p.size(); i++)
	{
		x = p[i].x + length;
		tp.clear();
		for (j = i; j < p.size(); j++)
		{
			if (p[j].x >= x)
				break;
			tp.push_back(p[j]);
		}
		sort(tp.begin(), tp.end(), cmpy);
		for (j = c - 1; j < tp.size(); j++)
		{
			if (tp[j].y - tp[j - c + 1].y < length)
			{
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int i;

	scanf("%d%d", &c, &n);
	p.resize(n);
	for (i = 0; i < n; i++)
	{
		scanf("%d%d", &p[i].x, &p[i].y);
	}
	sort(p.begin(), p.end(), 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;
}