#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>

using namespace std;

const double eps=1e-8;
const int maxn=1000+10;
const double maxx=2e10;
const double pi=acos(-1.0);
int top;

struct point{  
    //平面上的点 
    int x;
    int y;
    point(int x0=0,int y0=0)  
    {  
        //构造 
        x=x0;
        y=y0;
    }    
    
    point operator -(point b)          
    {
        //减    表示向量AB=A-B，实际运算B-A；
        return point(b.x-x,b.y-y);
    }
    
    int operator %(point b)        
    {
        //叉积 
        return x*b.y-y*b.x;
    }
}Null;


point yd(0,0);
int st[maxn];
point pp[maxn];
int n1;
point pt;
int pnum;

double dist(point p1,point p2)
{
    double px,py;
    px=p1.x-p2.x;
    py=p1.y-p2.y;
    return sqrt(px*px+py*py);
}

bool operator <(const point a,const point b)
{
    int m=(pp[0]-a)%(pp[0]-b);
    if(m>0)
    {
        return true;
    }
    else if(m==0&&(dist(pp[0],a)>dist(pp[0],b)))
    {
        return true;
    }
    return false;
}

void graham(int n)     
{
    //三个以上的点集，以排序按Y-X 
    top=2;
    st[0]=0;
    st[1]=1;
    st[2]=2;
    int i;
    for(i=2;i<=n;i++)
    {
        while((pp[st[top-1]]-pp[st[top]])%(pp[i]-pp[st[top-1]])>=0)
        {
            if(top==0)break;
            top--;
        }
        top++;
        st[top]=i; 
    }
    return ;
}

void init()
{
    int i;
    pt.y=-1;
    for(i=0;i<n1;i++)
    {
        scanf("%d %d",&pp[i].x,&pp[i].y);
        if(pt.y==-1||pp[i].y<pt.y)
        {
            pt=pp[i];
            pnum=i;
        }
        if(pp[i].y==pt.y&&pp[i].x<pt.x)
        {
            pt=pp[i];
            pnum=i;
        }
    }    
    swap(pp[pnum],pp[0]);
    sort(pp+1,pp+n1);
    pp[n1]=pp[0];
    return ;
}

void work(int n)
{
	bool ok=true;
	if(top<2)
	{
		ok=false;
	}
	int i;
	for(i=2;i<top;i++)
	{
		if(st[i]-st[i-1]==1)
		{
			ok=false;
			break;
		}
	}
	if(i==top&&fabs((pp[n-1]-pp[n-2])%(pp[n-1]-pp[n]))>eps)
	{
		ok=false;
	}
	if(ok)
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	return ;
}
int main()
{
	int t;
	scanf("%d",&t);
    while(t--)
    {
		scanf("%d",&n1);
        init();
        if(n1<6)
        {
			printf("NO\n");
		}
		else
		{
        	graham(n1);
        	work(n1);
		}
    }
    //system("pause");
    return 0;
}

• Re:求大神指点 (2762) 201141843309 2012-09-24 16:49:23
• Re:求大神指点 (2762) 201141843309 2012-09-24 16:49:26