POJ_1228
首先说明几点，第一，这个题目用long long int就可以了，不必像discuss说的那样非要用double不可，long long int如果都超了的话，用double计算出的精度也就值得怀疑了，第二，这个题目应该没有所有点都共线的数据，因为我不加那个判断也可以AC，但根据题意来看，应该还是要判断一下的。
这个题的题意感觉太费解了，后来折腾来折腾去我就直接按别人理解的去做了：判断凸包上的每条边至少包含3个点。
首先显然n<6是不可能的，因为最后需要是一个凸多边形，那么至少有3个顶点，再加上每条边上的1个点，一共是6个点。
之后，一个思路就是把这些点的逆时针序或者顺时针序找到，这一点可以借助凸包算法来完成，然后我们只要扫描一遍所有的边（两个相邻的点形成的边）即可。设当前边为i，前一条边为i-1，后一条边为i+1，如果i-1、i+1和i的夹角都不为0的话，那么边i就是一条只有两个点的边了，如果扫描完所有边之后都没有发现只包含两个点的边的话，就输出YES，否则输出NO。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 2010
#define zero 1e-8
struct point
{
int x, y;
}p[MAXD], res[MAXD];
int N, P, ok;
int cmp(const void *_p, const void *_q)
{
point *p = (point *)_p, *q = (point *)_q;
if(p->y == q->y)
return p->x < q->x ? -1 : 1;
return p->y < q->y ? -1 : 1;
}
void init()
{
int i, j, k;
scanf("%d", &N);
for(i = 0; i < N; i ++)
scanf("%d%d", &p[i].x, &p[i].y);
qsort(p, N, sizeof(p[0]), cmp);
}
long long int det(int x1, int y1, int x2, int y2)
{
return (long long int)x1 * y2 - (long long int)x2 * y1;
}
int del(int top, int i)
{
if(det(res[top].x - res[top - 1].x, res[top].y - res[top - 1].y, p[i].x - res[top].x, p[i].y - res[top].y) < 0)
return 1;
return 0;
}
int graham()
{
int i, j, k, top = 1, mint;
res[0] = p[0], res[1] = p[1];
for(i = 2; i < N; i ++)
{
while(top && del(top, i))
-- top;
res[++ top] = p[i];
}
mint = top;
res[++ top] = p[N - 2];
for(i = N - 3; i >= 0; i --)
{
while(top != mint && del(top, i))
-- top;
res[++ top] = p[i];
}
return top;
}
int check(int i)
{
long long int t1, t2;
t1 = det(res[i + 1].x - res[i].x, res[i + 1].y - res[i].y, res[i + 2].x - res[i + 1].x, res[i + 2].y - res[i + 1].y);
t2 = det(res[i + 2].x - res[i + 1].x, res[i + 2].y - res[i + 1].y, res[i + 3].x - res[i + 2].x, res[i + 3].y - res[i + 2].y);
ok = ok || t1 || t2;
if(t1 && t2)
return 0;
return 1;
}
void solve()
{
int i, j, k;
P = graham();
res[P] = res[0], res[P + 1] = res[1], res[P + 2] = res[2];
ok = 0;
for(i = 0; i < P; i ++)
if(!check(i))
{
printf("NO\n");
return ;
}
if(!ok)
printf("NO\n");
else
printf("YES\n");
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
init();
if(N < 6)
printf("NO\n");
else
solve();
}
return 0;
}