见代码。
/*
凸包（稳定凸包）
题意：给出一些点，这些点要么是凸包的顶点要么是边上的。
证明每条边上都至少有3个点。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = ;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-; struct Point {
double x,y;
bool operator < ( const Point p ) const {
return y<p.y||(y==p.y&&x<p.x);
}
}res[ maxn ],pnt[ maxn ];
bool flag[ maxn ][ maxn ];//f[i][j]:点ij之间是否还有点
bool ok[ maxn ];//ok[i]:i是否是凸包的顶点 double xmult( Point sp,Point ep,Point op ){
return (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x);
} double dis2( Point a,Point b ){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
} double dis( Point a,Point b ){
return sqrt( dis2(a,b) );
} bool PointOnLine( Point a,Point L,Point R ){
return ( fabs(xmult( a,L,R ))<eps )&&( (a.x-L.x)*(a.x-R.x)<eps )&&( (a.y-L.y)*(a.y-R.y)<eps );
} int Garham( int n ){
int top = ;
sort( pnt,pnt+n );
if( n== ) return ;
else res[ ] = pnt[ ];
if( n== ) return ;
else res[ ] = pnt[ ];
if( n== ) return ;
else res[ ] = pnt[ ];
for( int i=;i<n;i++ ){
while( top>&&xmult( res[top],res[top-],pnt[i] )>= )
top--;
res[ ++top ] = pnt[ i ];
}
int tmp = top;
res[ ++top ] = pnt[ n- ];
for( int i=n-;i>=;i-- ){
while( top!=tmp&&xmult( res[top],res[top-],pnt[i] )>= )
top--;
res[ ++top ] = pnt[ i ];
}
return top;
} int main(){
int T;
scanf("%d",&T);
while( T-- ){
int n;
scanf("%d",&n);
for( int i=;i<n;i++ )
scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
if( n<= ){
puts("NO");
continue;
}//至少要6个点
int cnt = Garham( n );
memset( ok,false,sizeof( ok ) );
memset( flag,false,sizeof( flag ) );
for( int i=;i<n;i++ ){
for( int j=;j<cnt;j++ ){
if( pnt[i].x==res[j].x&&pnt[i].y==res[j].y ){
ok[ i ] = true;
break;
}
}
}
for( int i=;i<n;i++ ){
if( !ok[i] ){
for( int j=;j<cnt;j++ ){
if( PointOnLine( pnt[i],res[j],res[(j+)%cnt]) ){
flag[ j ][ (j+)%cnt ] = true;
}
}
}
}
bool ans = true;
for( int i=;i<cnt;i++ ){
if( flag[ i ][ (i+)%cnt ]==false ){
ans = false;
break;
}
}
if( ans ) printf("YES\n");
else puts("NO");
}
return ;
}