题目来源：
http://poj.org/problem?id=1228
题意：题目输入一个凸包上的点（没有凸包内部的点，要么是凸包顶点，要么是凸包边上的点），判断这个凸包是否唯一。所谓唯一就是判断能不能在原有凸包上加点，
得到一个更大的凸包，并且这个凸包包含原有凸包上的所有点。很容易得到，当一个凸包唯一时，凸包的每条边上都要有至少三个点，若只有两个点，则可以增加一个点，得到更大的凸包。
思路：直接求凸包，得到原来凸包顶点，去掉凸包边上的点，由于用graham求凸包的过程中要对点集List[]极角排序，最后只需判断求得的凸包上的点stack[] 本来在 原点集List[]按极角排序后的位置是否相邻，由于凸包的性质，需要特别判断 凸包中第一个和最后一个点 它们之间是否有点。 另外， 若求得凸包中的点个数为2，则输入的所有点都在一条线上，这时需输出NO。
代码如下：
#include <iostream> #include <algorithm> #include <stdlib.h> #include <iostream> #include <stdio.h> #include <stack> #include <string> #include <string.h> #include <algorithm> #include <stdlib.h> #include <vector> #include <set> #include <math.h> #include <cmath> #include <map> #include <queue> using namespace std ; typedef long long LL; const int N = 1010; double EPS= 1e-10; double add(double a, double b) { if( fabs(a+b)< EPS * ( fabs(a)+fabs(b) ) ) return 0; return a+b; } struct Point{ double x,y; Point(){} Point(double _x, double _y):x(_x),y(_y){} Point operator + (Point p){ return Point( add(x,p.x), add( y,p.y ) ); } Point operator -(Point p){ return Point( add(x,-p.x), add(y, -p.y) ); } double operator^(Point p){ return add(x*p.y, -y*p.x ); } friend istream& operator>>(istream& is, Point& p){ is>>p.x>>p.y; return is; } double dist(Point p){ return sqrt( add( ( x-p.x)*(x-p.x) , (y-p.y)*(y-p.y) ) ); } }; Point List[N]; // 点集 int top; // 栈顶指针 int state[N]; // 栈中放的凸包点 原本 在点集按极角排序后的点集合中的位置（指针） bool cmp(Point a, Point b) // 按y轴值从小到大， y轴值相同时，x轴从小到大排列 { if(a.y != b.y) return a.y < b.y; else return a.x < b.x; } bool operator < (Point a, Point b) // 极角排序 { double tmp= (a-List[0])^(b-List[0]); if(tmp > 0) return 1; else if(tmp== 0 && a.dist(List[0]) <b.dist(List[0]) ) return 1; return 0; } void init(int n) { for(int i=0 ; i<n ;i++) cin>>List[i]; sort(List, List+n,cmp);// 排序后 List[0]为最左下方的点 sort(List+1 , List+n ); // 对List[1,n-1] 中的点进行极角排序，为凸包做准备 } void graham(int n) { state[0]=0; state[1]=1; top=1; double t; for(int i=2 ; i< n ; i++){ while(top >= 1 && ( (List[state[top] ]-List[ state[top-1] ] )^(List[i]-List[ state[top-1]] ) ) <=0 ) top--; // 不是凸包中的点出栈 top++;// 点i进栈 state[top]=i; // 记录点i进栈的 原本位置 i } } int main() { int t; cin>>t; while(t--) { int n; memset(state,-1,sizeof(state)); cin>>n; init(n); graham(n); if(top==1) { printf("NO "); continue; } int i; int flag=0; for( i=1; i<= top; i++) // 判断凸包顶点【0-1-2-...-top】是否相邻 { if( (state[i-1] +1) == state[i] ){ flag=1; break; } } for(i=1 ; i<n-1 ; i++) // 判断 凸包中最后一个顶点和 第一个顶点是否相邻 { if( ((List[n-1]-List[0])^(List[i]-List[0])) == 0 ) break; } if(i <n-1 && !flag ) printf("YES "); else printf("NO "); } return 0; }