首页 > 代码库 > POJ1228 稳定凸包

POJ1228 稳定凸包

对于共线凸包,暂时没有找到一种比较好的实现方法。

  本题对于共线是直接O(n^2)的方法直接刷一遍的,判断点在凸包边上的个数是否<3则NO,否则YES

  要注意到,对于一条直线,要特判。(不过按理说庄园怎么能够是一条直线呢?)

 

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <utility>#include <stack>#include <queue>#include <map>#include <deque>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define INF 0x3f3f3f3f#define MAXN 2005using namespace std;const double eps = 1e-8;const double PI = acos(-1.0);int sgn(double x){    if(fabs(x) < eps) return 0;    if(x < 0) return -1;    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;    }    bool operator ==(const Point &B) const    {        return fabs(B.x-x)<eps && fabs(B.y-y)<eps;    }    bool operator !=(const Point &B) const    {        return !((*this) == B);    }    double norm()//向量的模    {        return sqrt(x*x+y*y);    }    void transXY(double B) //绕原点逆时针旋转B弧度    {        double tx = x, ty = y;        x = tx*cos(B) - ty*sin(B);        y = tx*sin(B) + ty*cos(B);    }    void input() //读入只能用double读入    {        scanf("%lf%lf",&x,&y);    }};struct Line{    Point s,e;    Line(){}    Line(Point _s, Point _e)    {        s=_s; e=_e;    }};double dist(Point a, Point b){    return sqrt((a-b)*(a-b));}//判断点在线段上bool OnS(Point A, Line a){    return        sgn((a.s-A)^(a.e-A)) == 0 &&        sgn((A.x-a.s.x)*(A.x-a.e.x)) <= 0 &&        sgn((A.y-a.s.y)*(A.y-a.e.y)) <= 0;}//求凸包 Graham算法//点的编号0~n-1//返回凸包结果Stack[0~top-1]为凸包的编号//一个点或两个点 则凸包为一或二个点int Stack[MAXN],top;Point vertex[MAXN];bool Graham_cmp(Point A, Point B){    double tmp=(A-vertex[0])^(B-vertex[0]);    if(sgn(tmp) > 0) return 1;    if(sgn(tmp) == 0 && sgn(dist(A,vertex[0])-dist(B,vertex[0])) <= 0) return 1;    return 0;}void Graham(int n){    int k=0;    for(int i=1; i<n; i++)        if((vertex[k].y>vertex[i].y) || (vertex[k].y==vertex[i].y && vertex[k].x>vertex[i].x))            k=i;    swap(vertex[0], vertex[k]);    sort(vertex+1, vertex+n, Graham_cmp);    if(n == 1)    {        top=1;        Stack[0]=0;        return;    }    if(n == 2)    {        top=2;        Stack[0]=0;        Stack[1]=1;        return;    }    Stack[0]=0;    Stack[1]=1;    top=2;    for(int i=2; i<n; i++)    {        while(top > 1 && sgn((vertex[Stack[top-1]]-vertex[Stack[top-2]])^(vertex[i]-vertex[Stack[top-2]])) <= 0)            top--;        Stack[top++]=i;    }}int main(){    int tt,n;    scanf("%d",&tt);    while(tt--)    {        scanf("%d",&n);        for(int i=0; i<n; i++)            vertex[i].input();        Graham(n);        bool flag=1;        for(int i=0; i<top; i++)        {            int num=0;            for(int j=0; j<n; j++)                if(OnS(vertex[j],Line(vertex[Stack[i]],vertex[Stack[(i+1)%top]])))                    num++;            if(num<3)             {                flag=0;                break;            }        }        if(flag && top>=3) printf("YES\n");        else printf("NO\n");    }    return 0;}
View Code