稳定凸包

转载自这里

稳定的凸包:

比如有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");
   }
}