稳定的凸包:
比如有4个点：
这四个点是某个凸包上的部分点，他们连起来后确实还是一个凸包。
但是原始的凸包可能不是这样。比如：
即这四个点构成的凸包不算做“稳定”的。我们发现，当凸包上存在一条边上的点只有端点两个点的时候，这个凸包不是稳定的，因为它可以在这条边外再引入一个点，构成一个新的凸包。但一旦一条边上存在三个点，那么不可能再找到一个点使它扩展成一个新的凸包，否则构成的新多边形将是凹的。
下面是一个典型的稳定凸包：
判断是否稳定凸包的方法：
求出给定这堆点的新的凸包，然后判断凸包上的每条边上是否至少有3个点存在，假如有一条边不符合条件，那么就不是稳定凸包。
D - Grandpa's Estate
题意：
爷爷留了块土地给我，然而这块土地是以一些钉子来界定的，题目要做的就是给你一堆钉子的坐标（也就是凸包上部分的点），然后问你能不能唯一确定这块土地。
题解：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=1010;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
Point in[MAXN],out[MAXN];
typedef Point Vector;
Vector operator -(Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
bool operator <(const Point &a,const Point &b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
int convexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++)
{
while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--;//共线的点也要求出来
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--;//共线的点也要求出来
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
bool judge(int n)
{
for(int i=0;i<n;i++)
{
if(cross(out[i]-out[(i-1+n)%n],out[(i+1)%n]-out[i])!=0&&cross(out[(i+1)%n]-out[i],out[(i+2)%n]-out[(i+1)%n])!=0)
return false;//两个叉积都不为0，说明这条边只有两个顶点。
}
return true;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&in[i].x,&in[i].y);
}
if(n<6)
{
printf("NO\n");
continue;
}
int ans=convexHull(in,n,out);
if(judge(ans)) printf("YES\n");
else printf("NO\n");
}
}
