学步园

题目链接：http://poj.org/problem?id=1696

第一次自己写卷包裹算法的实现，没想到调试过程如此艰难曲折……

至此某题目推荐中的凸包初级题全部刷完。

题意及分析参见：http://blog.csdn.net/lyy289065406/article/details/6648614

#include <cstdio>

int n,loc,ans;
struct Point
{
   int x,y,id;
   bool flag;
}pt[55],ch[55];

int cross (Point p,Point q,Point x)
{  
    return (p.x-x.x)*(q.y-x.y)-(q.x-x.x)*(p.y-x.y);
} 

bool dis (Point p,Point q,Point x)
{
    return (p.x-x.x)*(p.x-x.x)+(p.y-x.y)*(p.y-x.y) < (q.x-x.x)*(q.x-x.x)+(q.y-x.y)*(q.y-x.y);
}

void Gift ()
{
	int i;
	ch[0]=pt[loc];
    ans=0;
    pt[loc].flag=false;
    while (ans!=n-1)
    {
		for (i=0;i<n;i++)   //寻找当前基点loc,取任意没标记的点就可以了
			if (pt[i].flag)
			{
				loc=i;
				break;
			}
		for (i=0;i<n;i++)
			if (i!=loc && pt[i].flag)
			{
				int temp=cross(pt[loc],pt[i],ch[ans]);
				if (temp < 0)
					loc=i;
				else if (temp == 0 && dis(pt[i],pt[loc],ch[ans]))
					loc=i;
			}
		ch[++ans]=pt[loc];
		pt[loc].flag=0;
    }
}

int main ()
{
	int T,i;
    scanf("%d",&T);
    while (T--)
    {
		scanf("%d",&n);
		for (i=0;i<n;i++)
		{
			scanf("%d%d%d",&pt[i].id,&pt[i].x,&pt[i].y);
			pt[i].flag=true;
			if (pt[i].y < pt[loc].y || pt[loc].y == pt[i].y && pt[i].x < pt[loc].x) //记录y值最小的点,有多个时,选x最小的
				loc=i;
		}
		Gift ();
		printf("%d",ans+1);
		for (i=0;i<=ans;i++)
			printf(" %d",ch[i].id);
		printf("\n");
	}
    return 0;
}