题目链接：https://vjudge.net/problem/POJ-1228
题意：我是真的没看懂题意QAQ。。。搜了才知道。题目给了n个点，问这n个点确定的凸包是否能通过添加点来变成一个新的凸包。也就是这个凸包是否稳定，稳定输出YES，否则输出NO。
思路：
首先给出结论，一个凸包稳定当且仅当它的每一条边上都有>=3个点。因为如果只有两个点的话，那么在这条边之外取一个点就能扩展出一个更大的凸包。而每条边上都有>=3个点时，此时扩展时会使得凸包变凹！
所以我们需要改一下求凸包的模板，只用将while中的<=改成< 即可，但这不能将最后一条边上的多个点保留 ，因为排序时将距离近的点排在前面 ，那么最后一条边上的点仅有距离最远的会被保留，其余的会被出栈。所以最后一条边需要特判。（网上许多代码没有特判，仅仅只是在判断的时候忽略了最后一条边，然而数据弱，没有卡这个点，所以能AC）。
求凸包之后需要判断每条边是不是由>=3个点。可以利用叉积判断点i处和点(i+1)处的夹角是否都不为0来判断，如果都不为0那么边(i , i+1)就不满足条件，因为前面特判了最后一条边(top , 0)，所以这里枚举判断时就不用枚举最后一条边了。
AC code：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int maxn=1005; const double PI=acos(-1.0); struct Point{ int x,y; Point():x(0),y(0){} Point(int x,int y):x(x),y(y){} }list[maxn]; int stack[maxn],top,flag; //计算叉积p0p1×p0p2 int cross(Point p0,Point p1,Point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } //计算p1p2的距离 double dis(Point p1,Point p2){ return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y)); } //极角排序函数，角度相同则距离小的在前面 bool cmp(Point p1,Point p2){ int tmp=cross(list[0],p1,p2); if(tmp>0) return true; else if(tmp==0&&dis(list[0],p1)<dis(list[0],p2)) return true; else return false; } //输入，把最左下角放在list[0]，并且进行极角排序 void init(int n){ Point p0; scanf("%d%d",&list[0].x,&list[0].y); p0.x=list[0].x; p0.y=list[0].y; int k=0; for(int i=1;i<n;++i){ scanf("%d%d",&list[i].x,&list[i].y); if((p0.y>list[i].y)||((p0.y==list[i].y)&&(p0.x>list[i].x))){ p0.x=list[i].x; p0.y=list[i].y; k=i; } } list[k]=list[0]; list[0]=p0; sort(list+1,list+n,cmp); } //graham扫描法求凸包，凸包顶点存在stack栈中 //从栈底到栈顶一次是逆时针方向排列的 void graham(int n){ if(n==1){ top=0; stack[0]=0; return; } top=1; stack[0]=0; stack[1]=1; for(int i=2;i<n;++i){ while(top>0&&cross(list[stack[top-1]],list[stack[top]],list[i])<0) --top; stack[++top]=i; } if(cross(list[n-2],list[n-1],list[0])!=0) //特判最后一条边 flag=0; } bool check(){ for(int i=0;i<top;++i){ if(cross(list[stack[(i+top)%(top+1)]],list[stack[i]],list[stack[(i+1)%(top+1)]])!=0&& cross(list[stack[i]],list[stack[(i+1)%(top+1)]],list[stack[(i+2)%(top+1)]])!=0) return false; } return true; } int T,n; int main(){ scanf("%d",&T); while(T--){ flag=1; scanf("%d",&n); init(n); if(n<6){ printf("NO\n"); continue; } graham(n); if(!flag){ printf("NO\n"); continue; } if(check()) printf("YES\n"); else printf("NO\n"); } return 0; }
原文：https://www.cnblogs.com/FrankChen831X/p/11827964.html