1228.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include<vector>
#include<algorithm>
using namespace std;
#define Type long
struct point
{long x,y;};

point p[1001];

int cheng(point &a,point &b,point &c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
int cmp_x_y(point a,point b)
{return a.y<b.y||(a.y==b.y&&a.x<b.x);}

void sort(point *a,int n)
{sort(&a[0],&a[n],cmp_x_y);}


int convex(point *p,int n,point *wall)
{int i;int st;Type h;
int stack[1001],sign[1001];

st=0;
stack[st++]=0;
stack[st++]=1;

for(i=0;i<n;i++)sign[i]=0;

sign[1]=1;
i=2;

while(i<n)
	{while(st>=2&&(h=cheng(p[stack[st-1]],p[stack[st-2]],p[i]))>0)
			{st--;if(h)sign[stack[st]]=0;}
	stack[st++]=i;sign[i]=1;i++;
	}

i--;

while(i>=0)
	{while(sign[i])i--;
	
	 while(st>=2&&cheng(p[stack[st-1]],p[stack[st-2]],p[i])>0)st--;
	 
	 stack[st++]=i;
	 i--;
	}

st--;

if(wall){for(i=0;i<st;i++)wall[i]=p[stack[i]];}

return st;
}
/////////////////////////////

int main()
{int i,j,tt,n,m;
point t[1001];
cin>>tt;
while(tt--)
{cin>>n;
	
	for(i=0;i<n;i++)cin>>p[i].x>>p[i].y;
	if(i<6){cout<<"NO"<<endl;continue;}
	
	sort(p,n);
	
	m=convex(p,n,t);

	
	if(m!=n)cout<<"NO"<<endl;
	else {for(i=0;i<n;i=j)
		{j=i+1;
	     while(cheng(t[i],t[(i+1)%n],t[(j+1)%n])==0)j++;
		if(j-i<2)break;
		}
		
		if(i<n)cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
		}
}
return 0;
}