4244594_tle.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 solve(vector <int> q, int status)
{
	int m = 1 << q.size();
	int i, j;
	int ret = 0x3fffffff;

	for (i = 0; i < q.size(); i++)
	{
		status ^= (1 << q[i]);
	}
	for (i = 0; i < m - 1; i++)
	{
		int tmp = status;
		for (j = 0; j < q.size(); j++)
		{
			if (i & (1 << j))
			{
				status |= (1 << q[j]);
			}
		}
		if (f[status] < ret)
			ret = f[status];
		status = tmp;
	}
	return ret;
}

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

	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;
		f[0] = 0;
		for (i = 1; i < mx; i++)
		{
			int v = num(i);
			if (v == 1)
			{
				f[i] = 0x3fffffff;
				continue;
			}
			tp.clear();
			for (j = 0; j < n; j++)
			{
				if ((1 << j) & i)
				{
					tp.push_back(j);
				}
			}
			sort(tp.begin(), tp.end(), cmp);
			vector <int> tq;
			f[i] = 0x3fffffff;
			for (j = 1; j < tp.size(); j++)
			{
				int tmp = area(tp[0], tp[j]);

				if (point[tp[0]].first == point[tp[1]].first)
				{
					tq.clear();
					tq.push_back(tp[0]);
					tq.push_back(tp[j]);
					for (k = 0; k < tp.size(); k++)
					{
						if (k == 0 || k == j)
							continue;
						if (point[tp[k]].first == point[tp[0]].first + 1 &&
							(point[tp[k]].second == point[tp[0]].second ||
							point[tp[k]].second == point[tp[j]].second))
						{
							tq.push_back(tp[k]);
						}
					}
					f[i] = min(f[i], tmp + solve(tq, i));
					tq.clear();
					tq.push_back(tp[0]);
					tq.push_back(tp[j]);
					for (k = 0; k < tp.size(); k++)
					{
						if (k == 0 || k == j)
							continue;
						if (point[tp[k]].first == point[tp[0]].first - 1 &&
							(point[tp[k]].second == point[tp[0]].second ||
							point[tp[k]].second == point[tp[j]].second))
						{
							tq.push_back(tp[k]);
						}
					}
					f[i] = min(f[i], tmp + solve(tq, i));
					continue;
				}

				if (point[tp[0]].second == point[tp[1]].second)
				{
					tq.clear();
					tq.push_back(tp[0]);
					tq.push_back(tp[j]);
					for (k = 0; k < tp.size(); k++)
					{
						if (k == 0 || k == j)
							continue;
						if (point[tp[k]].second == point[tp[0]].second + 1 &&
							(point[tp[k]].first == point[tp[0]].first ||
							point[tp[k]].first == point[tp[j]].first))
						{
							tq.push_back(tp[k]);
						}
					}
					f[i] = min(f[i], tmp + solve(tq, i));
					tq.clear();
					tq.push_back(tp[0]);
					tq.push_back(tp[j]);
					for (k = 0; k < tp.size(); k++)
					{
						if (k == 0 || k == j)
							continue;
						if (point[tp[k]].second == point[tp[0]].second - 1 &&
							(point[tp[k]].first == point[tp[0]].first ||
							point[tp[k]].first == point[tp[j]].first))
						{
							tq.push_back(tp[k]);
						}
					}
					f[i] = min(f[i], tmp + solve(tq, i));
					continue;
				}

				tq.clear();
				tq.push_back(tp[0]);
				tq.push_back(tp[j]);
				for (k = 0; k < tp.size(); k++)
				{
					if (k == 0 || k == j)
						continue;
					if ((point[tp[k]].first == point[tp[0]].first &&
						point[tp[k]].second == point[tp[j]].second) ||
						(point[tp[k]].first == point[tp[j]].first &&
						point[tp[k]].second == point[tp[0]].second))
					{
						tq.push_back(tp[k]);
					}
				}
				f[i] = min(f[i], tmp + solve(tq, i));
			}
		}
		printf("%d\n", f[mx - 1]);
	}
	return 0;
}