题目：
Being the only living descendant of his grandfather, Kamran the Believer inherited all of the grandpa's belongings. The most valuable one was a piece of convex polygon shaped farm in the grandpa's birth village. The farm was originally separated from the neighboring farms by a thick rope hooked to some spikes (big nails) placed on the boundary of the polygon. But, when Kamran went to visit his farm, he noticed that the rope and some spikes are missing. Your task is to write a program to help Kamran decide whether the boundary of his farm can be exactly determined only by the remaining spikes.
Input
The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains an integer n (1 <= n <= 1000) which is the number of remaining spikes. Next, there are n lines, one line per spike, each containing a pair of integers which are x and y coordinates of the spike.
Output
There should be one output line per test case containing YES or NO depending on whether the boundary of the farm can be uniquely determined from the input.
Sample Input
1
6
0 0
1 2
3 4
2 0
2 4
5 0
Sample Output
NO
题目大意：
给你n个点，问你是这n个点能否唯一确定一个凸包。
解题思路：
只要这n个点的凸包每一条边上至少有三个点，就可以，否则就是不可以。加一个点在线段上的判定。
特判一下n<6一定不成立的情况
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1005;
const double eps = 1e-8;
const double PI = acos(-1.0);
const int inf = 0x3f3f3f3f;
//对于浮点数的，><=0的判断。
int sgn(double x)
{
if(fabs(x)<eps) return 0;
if(x<0) return -1;
else 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);
}
Point operator +(const Point &b)const{
return Point(x+b.x,y+b.y);
}
//叉积
double operator ^(const Point &b)const{
return x*b.y-y*b.x;
}
//点积
double operator *(const Point &b)const{
return x*b.x+y*b.y;
}
//绕原点旋转角度B(弧度制)后，x,y的变化。
void transXY(double B)
{
double tx = x, ty = y;
x = tx*cos(B)-ty*sin(B);
y = tx*sin(B)+ty*cos(B);
}
};
struct Line{
Point s,e;
Line(){}
Line(Point _s, Point _e){
s = _s;
e = _e;
}
//两直线求交点
//第一个值为0表示直线重合，为1表示平行，为2表示相交
//只有第一个值为2时,交点才有意义。
pair<int,Point> operator &(const Line &b) const{
Point res = s;
if(sgn((s-e)^(b.s-b.e))==0)//两直线叉积为0
{
if(sgn((s-b.e)^(b.s-b.e))==0)
return make_pair(0,res); //重合
else return make_pair(1,res); //平行
}
double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));//线段长的比值等于两个面积比值
res.x+=(e.x-s.x)*t;
res.y+=(e.y-s.y)*t;
return make_pair(2,res);
}
};
double dist(Point a, Point b)
{
//勾股定理，使用点积
return sqrt((a-b)*(a-b));
}
Point p[maxn];
int n;
//做极角排序
bool _cmp(Point p1,Point p2)
{
double tmp = (p1-p[1])^(p2-p[1]); //向量叉乘
if(sgn(tmp)>0) return true;
else if(sgn(tmp)==0&&sgn(dist(p1,p[1])-dist(p2,p[1]))<=0)
return true;
else return false;
}
int Stack[maxn],top;
void Graham()
{
Point p0;
int k = 1;
p0 = p[1];
//找最下方的一个点
for(int i = 2; i <= n; i++)
{
if(p0.y>p[i].y||(p0.y==p[i].y&&p0.x>p[i].x))
{
p0 = p[i];
k = i;
}
}
swap(p[1],p[k]);
sort(p+2,p+n+1,_cmp);
if(n == 1)
{
top = 1;
Stack[0] = 1;
return ;
}
if(n == 2)
{
top = 2;
Stack[0] = 1;
Stack[1] = 2;
return ;
}
Stack[0] = 1;
Stack[1] = 2;
top = 2;
for(int i = 3; 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;
}
}
//判断点在线段上面
bool OnSeg(Point P,Line L)
{
return
sgn((L.s-P)^(L.e-P))==0&&
sgn((P.x-L.e.x)*(P.x-L.s.x))<=0&&
sgn((P.y-L.e.y)*(P.y-L.s.y))<=0;
}
int solve()
{
Stack[top] = 1;
int cnt;
for(int i = 0; i < top; i++)
{
cnt = 0;
Line line = Line(p[Stack[i]],p[Stack[i+1]]);
for(int j = 1; j <= n; j++)
{
if(OnSeg(p[j],line))
cnt++;
}
if(cnt<3)
return 0;
}
return 1;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
}
if(n<6)
{
printf("NO\n");
continue;
}
Graham();
if(solve())
{
printf("YES\n");
}
else
printf("NO\n");
}
return 0;
}