1704.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>

struct point 
{
	char name[2];
	int x;
	int y;
};
int abs(int t)
{
	if(t>0)return t;
	else return -t;
}

int area(point &a,point &b,point &c)
{
	return a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y;
}
int dot(point &a,point &b,point &c)
{
	return (a.x-c.x)*(b.x-c.x)+(a.y-c.y)*(b.y-c.y);
}

int main()
{
	point p[30];
	int n;
	int i,j,k,l;
	int sum;
	int flag,c1,c2,c3,d1,d2,d3;
	int ri,rj,rk;
	while(scanf("%d",&n))
	{
		if(n==0)break;
		for(i=1;i<=n;i++)
			scanf("%s%d%d",p[i].name,&p[i].x,&p[i].y);
		sum=0;
		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
				for(k=j+1;k<=n;k++)
				{
					flag=1;
					for(l=1;l<=n;l++)if(l!=i && l!=j && l!=k)
					{
						c1=area(p[i],p[j],p[l]);
						c2=area(p[j],p[k],p[l]);
						c3=area(p[k],p[i],p[l]);
						if(c1>0 && c2>0 && c3>0){flag=0;break;}
						if(c1<0 && c2<0 && c3<0){flag=0;break;}
						d1=dot(p[i],p[j],p[l]);
						d2=dot(p[j],p[k],p[l]);
						d3=dot(p[k],p[i],p[l]);
						if(c1==0 && d1<=0){flag=0;break;}
						if(c2==0 && d2<=0){flag=0;break;}
						if(c3==0 && d3<=0){flag=0;break;}
					}
					if(flag==1 &&sum<abs(area(p[i],p[j],p[k]))){sum=abs(area(p[i],p[j],p[k]));ri=i;rj=j;rk=k;}

				}
				printf("%s%s%s\n",p[ri].name,p[rj].name,p[rk].name);
	}
	return 0;
}