pku1569.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>

typedef struct 
{
	int x, y;
}Point;

Point p[20];
int N;

int det(int x1, int y1, int x2, int y2)
{
	return x1 * y2 - x2 * y1;
}

int cross(Point a, Point b, Point c)
{
	return det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

int ABS(int x)
{
	return x > 0 ? x : -x;
}

int Test(Point a, Point b, Point c, Point d)
{
	if (cross(b, d, a) * cross(b, d, c) > 0)
	{
		return 1;
	}
	if (cross(a, d, b) * cross(a, d, c) > 0)
	{
		return 1;
	}
	if (cross(c, d, a) * cross(c, d, b) > 0)
	{
		return 1;
	}
	return 0;
}

void Solve()
{
	int i, j, k, m;
	int maxa, im, jm, km, tmpa;
	maxa = 0;
	for (i = 0; i < N; i++)
	{
		for (j = i + 1; j < N; j++)
		{
			for (k = j + 1; k < N; k++)
			{
				tmpa = det(p[i].x, p[i].y, p[j].x, p[j].y)
					+  det(p[j].x, p[j].y, p[k].x, p[k].y)
					+  det(p[k].x, p[k].y, p[i].x, p[i].y);
				tmpa = ABS(tmpa);
				if (tmpa > maxa)
				{
					for (m = 0; m < N; m++)
					{
						if (m == i || m == j || m == k)
						{
							continue;
						}
						if (Test(p[i], p[j], p[k], p[m]) == 0)
						{
							break;
						}
					}
					if (m == N)
					{
						maxa = tmpa;
						im = i;
						jm = j;
						km = k;
					}
				}
			}
		}
	}
	printf("%c%c%c\n", im + 'A', jm + 'A', km + 'A');
}

int main()
{
	int i;
	char c[2];
	while (scanf("%d", &N) != -1 && N)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%s %d %d", c, &p[i].x, &p[i].y);
		}
		Solve();
	}
	
	return 0;
}