题意：原先有一个由钉子和绳子圈定的凸多边形，然后绳子和钉子有所丢失，判断剩余的钉子是否能够确定原先的凸多边形；
转化：满足的条件：剩余的钉子能够组成凸包，而且每个边上至少有三个钉子；至少剩余六个钉子，凸包至少有三个顶点；
算法：凸包构造，暴力判断每一条边上是否有三个点；//数据范围是1000，n^2
凸包的理解：
#include<iostream> #include<cmath> #include<algorithm> #include<cstdio> using namespace std; const int MAXN =1010;//这是点的个数，rt的时候检查这里 const double PI= acos(-1.0); //精度 double eps=1e-8; //避免出现-0.00情况，可以在最后加eps //精度比较 int sgn(double x) { if(fabs(x)<=eps)return 0; if(x<0)return -1; return 1; } //点的封装 struct Point { double x,y; Point (){} //赋值 Point (double _x,double _y) { x=_x; y=_y; } //点相减 Point operator -(const Point &b)const { return Point (x-b.x,y-b.y); } //点积 double operator *(const Point &b)const { return x*b.x+y*b.y; } //叉积 double operator ^(const Point &b)const { return x*b.y-y*b.x; } } ; //线的封装 struct Line { Point s,e; Line (){} Line (Point _s,Point _e) { s=_s; e=_e; } //平行和重合判断 相交输出交点 //直线相交和重合判断，不是线段， Point operator &(const Line &b)const{ Point res=b.s; if(sgn((e-s)^(b.e-b.s))==0) { if(sgn((e-s)^(e-b.e))==0) { //重合 return Point(0,0); } else { //平行 return Point(0,0); } } double t=((e-s)^(s-b.s))/((e-s)^(b.e-b.s)); res.x+=(b.e.x-b.s.x)*t; res.y+=(b.e.y-b.s.y)*t; return res; } }; //向量叉积 double xmult(Point p0,Point p1,Point p2) { return (p0-p1)^(p2-p1); } //线段和线段非严格相交，相交时true //此处是线段 bool seg_seg(Line l1,Line l2) { return sgn(xmult(l1.s,l2.s,l2.e)*xmult(l1.e,l2.s,l2.e))<=0&&sgn(xmult(l2.s,l1.s,l1.e)*xmult(l2.e,l1.s,l1.e))<=0; } //两点之间的距离 double dist(Point a,Point b) { return sqrt((a-b)*(a-b)); } //极角排序;对100个点进行极角排序 int pos;//极点下标 Point p[MAXN]; int Stack[MAXN],top; bool cmp(Point a,Point b) { double tmp=sgn((a-p[pos])^(b-p[pos]));//按照逆时针方向进行排序 if(tmp==0)return dist(a,p[pos])<dist(b,p[pos]); if(tmp<0)return false ; return true; } void Graham(int n) { Point p0; int k=0; p0=p[0]; for(int i=1;i<n;i++)//找到最左下边的点 { if(p0.y>p[i].y||(sgn(p0.y-p[i].y))==0&&p0.x>p[i].x) { p0=p[i]; k=i; } } swap(p[k],p[0]); sort(p+1,p+n,cmp); if(n==1) { top=2; Stack[0]=0; return ; } if(n==2) { top=2; Stack[0]=0; Stack[1]=1; return ; } Stack[0]=0;Stack[1]=1; top=2; for(int i=2;i<n;i++) { while(top>1&&sgn((p[Stack[top-1]]-p[Stack[top-2]])^(p[i]-p[Stack[top-2]]))<=0) top--; Stack[top++]=i; } } int n; bool check() { if(n<6)return false; if(top<2)return false; for(int i=0;i<top-1;i++) { int ans=0; for(int j=0;j<n;j++) if(xmult(p[j],p[Stack[i]],p[Stack[i+1]])==0) ans++; if(ans<3) return false; } return true ; } int main () { int t; cin>>t; while(t--) { cin>>n; for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y; Graham(n);//n和top都是指点的个数 if(check()) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }