pku1696.cpp

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

#include <stdio.h>
#define TheMax 1000000
typedef struct 
{
	int x, y;
} Point;

Point p[100];

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

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

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

void Solve()
{
	int N;
	int i, j, next, last, ans;
	int st[100];
	scanf("%d", &N);
	p[0].y = TheMax;
	for (i = 1; i <= N; i++)
	{
		scanf("%d %d %d", &last, &p[i].x, &p[i].y);
		st[i] = 0;
		if (p[i].y < p[0].y)
		{
			p[0].y = p[i].y;
		}
	}
	printf("%d ", N);
	p[0].x = 0;
	st[0] = 1;
	for (i = 0, last = 0; i < N; i++)
	{
		j = 0;
		while (st[j])
			j++;
		next = j;
		j++;
		for (; j <= N; j++)
		{
			if (st[j] == 0)
			{
				ans = det(p + last, p + next, p + j);
				if (ans < 0)
				{
					next = j;
				}
				else if (ans == 0 && ABS(p[last].x - p[next].x) > ABS(p[last].x - p[j].x))
				{
					next = j;
				}
			}
		}
		st[next] = 1;
		last = next;
		printf("%d ", last);
	}
	printf("\n");
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		Solve();
	}
	return 0;
}