学步园

给你凸包上的一些点，求是否可以确定一个凸包。

开始木有理解哇，><，以为只要这个点等于求得凸包的点就可以了，后来发现不对。如果一个凸包的边只有两个点，那么如果外界还有一个点，可能这个凸包就不确定了，相当于，两个钉子之间有个皮筋，但是外面还有个钉子的话，皮筋就可以拉到那个钉子上，而且满足题意。

因此，需要满足凸包每条边必须有三个点，这样的话，如果外界还有点的话，拉的话，就不是凸多边形了，自己可以模拟下。

根据这个 ，看图

判断凸包上三点这个，我做的比较麻烦，分两种情况，如果在线段上（不在端点），可以，如果和这两点共线（不在端点），也可以。

后来想了下，既然题目已经给出的是凸包的点，那就不用graham算法了吧？改了改，不对。因为我需要按顺序去判断凸包的边，如果仅仅是排序，排不出来按顺时针或者逆时针的情况><。。。

测了下，数据弱了，不存在全部都共线的case。。。我还判断了呢。。。

#include <queue><br /> #include <stack><br /> #include <math.h><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <limits.h><br /> #include <string.h><br /> #include <algorithm><br /> using namespace std;<br /> const int MAX = 1010;<br /> const double eps = 1e-6;<br /> struct point{ double x,y;};<br /> point p[MAX];<br /> int stk[MAX];<br /> int top;<br /> bool dy(double x,double y) { return x > y + eps;} // x > y<br /> bool xy(double x,double y) { return x < y - eps;} // x < y<br /> bool dyd(double x,double y) { return x > y - eps;} // x >= y<br /> bool xyd(double x,double y) { return x < y + eps;} // x <= y<br /> bool dd(double x,double y) { return fabs( x - y ) < eps;} // x == y<br /> double crossProduct(point a,point b,point c)//向量 ac 在 ab 的方向<br /> {<br /> return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);<br /> }<br /> double disp2p(point a,point b)<br /> {<br /> return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );<br /> }<br /> bool cmp(point a,point b) // 第一次排序<br /> {<br /> if( dd(a.y ,b.y ) )<br /> return xy(a.x, b.x);<br /> return xy(a.y,b.y);<br /> }<br /> bool cmp1(point a,point b) // 第二次排序<br /> {<br /> double len = crossProduct(p[0],a,b);<br /> if( dd(len,0.0) )<br /> return xy(disp2p(p[0],a),disp2p(p[0],b));<br /> return xy(len,0.0);<br /> }<br /> bool is_polygon(point p[],int n)<br /> {<br /> if( n <= 2 )<br /> return false;<br /> for(int i=2; i<n; i++)<br /> if( !dd(crossProduct(p[0],p[1],p[i]),0.0) )<br /> return true;<br /> return false;<br /> }<br /> bool onSegment(point a, point b, point c)<br /> {<br /> double maxx = max(a.x,b.x);<br /> double maxy = max(a.y,b.y);<br /> double minx = min(a.x,b.x);<br /> double miny = min(a.y,b.y);<br /> if( dd(crossProduct(a,b,c),0.0) && dy(c.x,minx) && xy(c.x,maxx) && dy(c.y,miny) && xy(c.y,maxy) )<br /> return true;<br /> return false;<br /> }<br /> bool Graham(point p[],int n)<br /> {<br /> sort(p,p+n,cmp);<br /> sort(p+1,p+n,cmp1);<br /> top = 0;<br /> stk[top++] = 0;<br /> stk[top++] = 1;<br /> stk[top++] = 2;<br /> top--;<br /> for(int i=3; i<n; i++)<br /> {<br /> while( top != 0 )<br /> {<br /> point a,b;<br /> a = p[stk[top]];<br /> b = p[stk[top-1]];<br /> if( xyd( crossProduct(a,b,p[i]), 0.0 ) )<br /> top--;<br /> else<br /> break;<br /> }<br /> stk[++top] = i;<br /> }<br /> top++;<br /> for(int i=0; i<top; i++)<br /> {<br /> bool flag = 0;<br /> for(int k=0; k<n; k++)<br /> if( k != stk[i] && k != stk[(i+1)%top] )<br /> if( onSegment(p[stk[i]],p[stk[(i+1)%top]],p[k]) // 判断 在线段中间，或者和线段共线<br /> || dd(crossProduct(p[stk[i]],p[stk[(i+1)%top]],p[k]),0.0) )<br /> {<br /> flag = 1;<br /> break;<br /> }<br /> if( !flag )<br /> return false;<br /> }<br /> return true;<br /> }<br /> int main()<br /> {<br /> int ncases;<br /> int n;<br /> scanf("%d",&ncases);<br /> while( ncases-- )<br /> {<br /> scanf("%d",&n);<br /> for(int i=0; i<n; i++)<br /> scanf("%lf %lf",&p[i].x,&p[i].y);<br /> if( !is_polygon(p,n) || n <= 5 )<br /> {<br /> printf("NO/n");<br /> continue;<br /> }<br /> bool ans = Graham(p,n);<br /> if( ans )<br /> printf("YES/n");<br /> else<br /> printf("NO/n");<br /> }<br /> return 0;<br /> }<br />