3623244_ac_0ms_208k.cpp

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

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

using namespace std;

typedef pair <int, int> PII;

PII point[15];
int num;
bool mark[15];
typedef vector <PII> VP;
VP triangle (3);
double maxArea;
string res;

double area(PII a, PII b, PII c)
{
	return fabs(0.5 * ((a.second - c.second)
				* (b.first - c.first) 
				- (b.second - c.second)
				* (a.first - c.first)));
}

void solve()
{
	double tmp;
	string str = "";

	triangle.clear();
	for (int i = 0; i < num; i++)
	{
		if (mark[i] == true)
		{
			str += i + 'A';
			triangle.push_back(point[i]);
		}
	}
	tmp = area(triangle.at(0), triangle.at(1), triangle.at(2));
	for (int j = 0; j < num; j++)
	{
		if (mark[j] == false)
		{
			double total = 0.0;
			for (int i = 0; i < 3; i++)
			{
				total += area(point[j], triangle[i], triangle[(i + 1) % 3]);
			}
			if (total <= tmp)
			{
				return ;
			}
		}
	}
	if (tmp > maxArea)
	{
		maxArea = tmp;
		res = str;
	}
}

void dfs(int st, int n)
{
	if (n == 0)
	{
		solve();
		return ;
	}
	for (int i = st; i <= num - n; i++)
	{
		mark[i] = true;
		dfs(i + 1, n - 1);
		mark[i] = false;
	}
}

int main()
{
	int x, y;

	while (scanf("%d", &num) == 1 && num != 0)
	{
		maxArea = 0;
		for (int i = 0; i < num; i++)
		{
			scanf("%*s%d%d", &x, &y);
			point[i] = make_pair(x, y);
		}
		fill_n(mark, num, false);
		dfs(0, 3);
		puts(res.c_str());
	}
	return 0;
}