一个凸包丢了一些点，剩下的点能否表示原凸包？
先看一下什么情况下可以表示原凸包：现有的凸包每边都有3个以上的点。这样丢掉的点必定也在凸包上，否则现有的点不再凸包上，与已知不符。
做法就是根据所给点再算一次凸包，判断每边是否有三个以上的点。
注意，n<6为NO，所给点为直线为NO。
常用的凸包模版有时会包含边上的点（比如起始三点共线），有的时候不会。借此机会整理下自己的凸包哈！
//Memory: 260K
//Time: 0MS
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int top;
struct POINT
{
double x,y;
};POINT p[1005],ch[1005];
double dist(POINT a,POINT b)
{
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
double multiply(POINT sp,POINT ep,POINT op)
{
return (sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y);
}
bool online(POINT s,POINT e,POINT p)
{
return( (multiply(e,p,s)==0) && ( ( (p.x-s.x)*(p.x-e.x)<=0 ) &&
( (p.y-s.y)*(p.y-e.y)<=0 ) ) );
}
bool ptcmp(POINT a,POINT b)
{
if(multiply(a,b,p[0])>0 || (multiply(a,b,p[0])==0 && (dist(a,p[0])<dist(b,p[0]))))
return 1;
return 0;
}
void graham(int n)
{
int i,k=0;
top=1;
POINT temp;
for(i=1;i<n;i++)
if(p[i].y<p[k].y || (p[i].y==p[k].y && p[i].x<p[k].x))
k=i;
temp=p[0];
p[0]=p[k];
p[k]=temp;
sort(p+1,p+n,ptcmp);
ch[0]=p[0];
ch[1]=p[1];
for(i=2;i<n;i++)
{
while(top>=1 && multiply(p[i],ch[top],ch[top-1])>=0)
top--;
ch[++top]=p[i];
}
ch[++top]=p[0];
}
int main()
{
int cas,n;
cin>>cas;
while(cas--)
{
cin>>n;
int i,j,flag=0,k=0;
for(i=0;i<n;i++)
cin>>p[i].x>>p[i].y;
graham(n);
for(i=1;i<top-1;i++)
{
flag=0;
for(j=0;j<=n;j++)
{
if(online(ch[i],ch[i-1],p[j]))
flag++;
if(flag>=3)
break;
}
if(flag<3)
k=1;
}
if(n<=5)
k=1;
else
{
for(i=2;i<n;i++)
if(multiply(p[i-2],p[i-1],p[i])!=0)
break;
if(n==i)
k=1;
}
if(k!=1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}