4245946_wa.cpp

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

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

using namespace std;

int f[1 << 15];
int point[15][2];
int n;
int tp[15], c;

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][1] == point[b][1])
		return point[a][0] < point[b][0];
	return point[a][1] > point[b][1];
}

int area(int a, int b)
{
	if (point[a][0] == point[b][0])
		return ab(point[a][1] - point[b][1]);
	if (point[a][1] == point[b][1])
		return ab(point[a][0] - point[b][0]);
	return ab((point[a][1] - point[b][1]) * (point[a][0] - point[b][0]));
}

int solve(int q[], int len, int status)
{
	int m = 1 << len;
	int i, j;
	int ret = 0x3fffffff;

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

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

	while (scanf("%d", &n) == 1, n)
	{
		for (i = 0; i < n; i++)
		{
			scanf("%d%d", &point[i][0], &point[i][1]);
		}
		mx = 1 << n;
		f[0] = 0;
		for (i = 1; i < mx; i++)
		{
			//printf("%d\n", i);
			int v = num(i);
			if (v == 1)
			{
				f[i] = 0x3fffffff;
				continue;
			}
			c = 0;
			for (j = 0; j < n; j++)
			{
				if ((1 << j) & i)
				{
					tp[c++] = j;
				}
			}
			sort(tp, tp + c, cmp);
			int tq[15], q;
			f[i] = 0x3fffffff;
			for (j = 1; j < 2; j++)
			{
				int tmp = area(tp[0], tp[j]);

				if (point[tp[0]][0] == point[tp[1]][0])
				{
					q = 0;
					tq[q++] = tp[0];
					tq[q++] = tp[j];
					for (k = 0; k < c; k++)
					{
						if (k == 0 || k == j)
							continue;
						if (point[tp[k]][0] == point[tp[0]][0] + 1 &&
							(point[tp[k]][1] == point[tp[0]][1] ||
							point[tp[k]][1] == point[tp[j]][1]))
						{
							tq[q++] = tp[k];
						}
					}
					f[i] = min(f[i], tmp + solve(tq, q, i));
					q = 0;
					tq[q++] = tp[0];
					tq[q++] = tp[j];
					for (k = 0; k < c; k++)
					{
						if (k == 0 || k == j)
							continue;
						if (point[tp[k]][0] == point[tp[0]][0] - 1 &&
							(point[tp[k]][1] == point[tp[0]][1] ||
							point[tp[k]][1] == point[tp[j]][1]))
						{
							tq[q++] = tp[k];
						}
					}
					f[i] = min(f[i], tmp + solve(tq, q, i));
					continue;
				}

				if (point[tp[0]][1] == point[tp[1]][1])
				{
					q = 0;
					tq[q++] = tp[0];
					tq[q++] = tp[j];
					for (k = 0; k < c; k++)
					{
						if (k == 0 || k == j)
							continue;
						if (point[tp[k]][1] == point[tp[0]][1] + 1 &&
							(point[tp[k]][0] == point[tp[0]][0] ||
							point[tp[k]][0] == point[tp[j]][0]))
						{
							tq[q++] = tp[k];
						}
					}
					f[i] = min(f[i], tmp + solve(tq, q, i));
					q = 0;
					tq[q++] = tp[0];
					tq[q++] = tp[j];
					for (k = 0; k < c; k++)
					{
						if (k == 0 || k == j)
							continue;
						if (point[tp[k]][1] == point[tp[0]][1] - 1 &&
							(point[tp[k]][0] == point[tp[0]][0] ||
							point[tp[k]][0] == point[tp[j]][0]))
						{
							tq[q++] = tp[k];
						}
					}
					f[i] = min(f[i], tmp + solve(tq, q, i));
					continue;
				}

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