4243895_wa.cpp

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

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

using namespace std;

int f[1 << 15];
typedef pair <int, int> PII;
PII point[15];
int n;
vector <int> tp;

int num(int v)
{
	int ret = 0;

	while (v)
	{
		v &= v - 1;
		ret++;
	}
	return ret;
}

int min(int a, int b)
{
	return a < b ? a : b;
}

int ab(int v)
{
	return v < 0 ? -v : v;
}

bool cmp(int a, int b)
{
	if (point[a].second == point[b].second)
		return point[a].first < point[b].first;
	return point[a].second > point[b].second;
}

int area(int a, int b)
{
	if (point[a].first == point[b].first)
		return ab(point[a].second - point[b].second);
	if (point[a].second == point[b].second)
		return ab(point[a].first - point[b].first);
	return ab((point[a].second - point[b].second) * (point[a].first - point[b].first));
}

int main()
{
	int i, j, mx;
	int x, y;

	while (scanf("%d", &n) == 1, n)
	{
		for (i = 0; i < n; i++)
		{
			scanf("%d%d", &x, &y);
			point[i] = make_pair(x, y);
		}
		mx = 1 << n;
		for (i = 1; i < mx; i++)
		{
			int v = num(i);
			if (v == 1)
			{
				f[i] = 0;
				continue;
			}
			tp.clear();
			for (j = 0; j < n; j++)
			{
				if ((1 << j) & i)
				{
					tp.push_back(j);
				}
			}
			sort(tp.begin(), tp.end(), cmp);
			f[i] = 0xfffffff;
			for (j = 1; j < tp.size(); j++)
			{
				int tmp = area(tp[0], tp[j]);
				int v = (1 << tp[0]) ^ i;
				int s = (1 << tp[j]) ^ i;
				int t = (1 << tp[0]) & s;
				f[i] = min(f[i], tmp + min(f[v], min(f[s], f[t])));
			}
		}
		printf("%d\n", f[mx - 1]);
	}
	return 0;
}