3757061_ac_407ms_312k.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 75 行

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

using namespace std;

int n, c, m;
struct node
{
	int x, y;
}p[201];

vector <int> y;
vector <int> ::iterator it;
vector <int> ::reverse_iterator rit;
int ans;

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

void solve()
{
	int i, j, k;
	int miny, maxy;

	for (i = 0; i <= n - m; i++)
	{
		y.clear();
		miny = 1000000;
		maxy = -1;
		for (k = i; k < i + m; k++)
		{
			if (p[k].y > maxy)	maxy = p[k].y;
			if (p[k].y < miny)	miny = p[k].y;
			y.push_back(p[k].y);
		}
		int tmp = (maxy - miny + 2) * (p[i + m - 1].x - p[i].x + 2);
		if (tmp < ans)
			ans = tmp;
		for (j = i + m; j < n; j++)
		{
			y.push_back(p[j].y);
			sort(y.begin(), y.end());
			for (k = m - 1; k < y.size(); k++)
			{
				tmp = (y[k] - y[k-m+1] + 2) * (p[j].x - p[i].x + 2);
				if (tmp < ans)
					ans = tmp;
			}
		}
	}
}

int main()
{
	int cas;
	int i;

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