学步园

不做不知道，做了才发现凸包的模版错的太多了。。。。。

感谢cxlove的耐心纠错。。。。。。。终于能有个比较好的凸包模版了。。。。两页的WA。。。。。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<math.h>
#define zero(x) (((x)>0?(x):-(x))<eps)
#define eps 1e-8
#define val 1005
using namespace std;
typedef struct node{double x,y;}point;
int pos,n;
point p[val];
vector<point> s;
double dist(point p1,point p2)
{
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double xmult(point p1,point p2,point p0)
{
	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool cmp(const node &p1,const node &p2)
{
	double temp;
	temp=xmult(p[0],p1,p2);
	if(temp>0) return true;
	if(zero(temp)&&dist(p1,p[0])<dist(p2,p[0]))//距离小的靠前，通过远的弹出近的
		return true;
	return false;
}
void graham();
int main()
{
	int i,num,cnt,cas;
	bool flag;
	for(scanf("%d",&cas);cas;cas--)
	{
		scanf("%d",&n);
		s.clear();
		for(i=0;i<n;i++)
		{
			scanf("%lf%lf",&p[i].x,&p[i].y);
			if(p[i].y<p[0].y) swap(p[i],p[0]);
			else if(zero(p[i].y-p[0].y)&&p[i].x<p[0].x)
				swap(p[i],p[0]);
		}
		graham();
		s.push_back(s[0]);
		flag=false;
		if(n<=5) 
		{
			printf("NO\n");
			continue;
		}
		for(i=0;i<s.size()-1;i++)
		{
			cnt=0;
			for(int j=0;j<n;j++)
				if(zero(xmult(s[i],s[i+1],p[j])))   cnt++;
			if(cnt<3)
			{
				flag=true;
				break;
			}
		}
		for(i=2;i<n;i++)
			if(!zero(xmult(p[i],p[i-1],p[i-2]))) break;
		if(i>=n) flag=true;
		if(flag) printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}
void graham()
{
	int i,end;
	pos=0;
	sort(p+1,p+n,cmp);
	for(i=0;i<3;i++) s.push_back(p[i]);
	for(i=3;i<n;i++)
	{
		while(1)
		{
			end=s.size()-1;
			if(s.size()>=2&&xmult(s[end-1],s[end],p[i])<eps)//共线的就不要放了
				s.pop_back();
			else break;
		}
		s.push_back(p[i]);
	}
	return ;
}