POJ 1228 凸包惟一性判断（多边形模板）

1
6 
0 0
1 2
3 4
2 0
2 4 
5 0

NO

题意：判断凸包是否惟一。

思路：把凸包的结点先变成顶点，然后再判断两个顶点之间是否还有结点，如果有顶点，说明两个顶点之间的边是惟一的。如果顶点之间没有结点，所以这两个顶点之间可以有其他加入的结点让这个凸包不惟一。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 111116
#define eps 1e-7
using namespace std;
int sgn(const double &x){ return x < -eps? -1 : (x > eps);}
inline double sqr(const double &x){ return x * x;}
inline int gcd(int a, int b){ return !b? a: gcd(b, a % b);}
struct Point
{
    double x, y;
    Point(const double &x = 0, const double &y = 0):x(x), y(y){}
    Point operator -(const Point &a)const{ return Point(x - a.x, y - a.y);}
    Point operator +(const Point &a)const{ return Point(x + a.x, y + a.y);}
    Point operator *(const double &a)const{ return Point(x * a, y * a);}
    Point operator /(const double &a)const{ return Point(x / a, y / a);}
    bool operator < (const Point &a)const{ return sgn(x - a.x) < 0 || (sgn(x - a.x) == 0 && sgn(y - a.y) < 0);}
    bool operator == (const Point &a)const{ return sgn(sgn(x - a.x) == 0 && sgn(y - a.y) == 0);}
    friend double det(const Point &a, const Point &b){ return a.x * b.y - a.y * b.x;}
    friend double dot(const Point &a, const Point &b){ return a.x * b.x + a.y * b.y;}
    friend double dist(const Point &a, const Point &b){ return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
    void in(){ scanf("%lf %lf", &x, &y); }
    void out()const{ printf("%lf %lf\n", x, y); }
};
struct Line //线段类
{
    Point s, t;
    Line() {}
    Line(const Point &s, const Point &t):s(s), t(t) {}
    void in() { s.in(),t.in(); }
    double pointDistLine(const Point &p)
    {
        if(sgn(dot(t - s, p - s)) < 0)return dist(p, s);
        if(sgn(dot( s - t, p - t)) < 0)return dist(p, t);
        return fabs(det(t - s, p - s)) / dist(s, t);
    }
    bool pointOnLine(const Point &p)
    {
        return sgn(det(s - p, t - p)) == 0 && sgn(dot(s - p, t - p)) < 0;
    }
};
struct Poly //多边形类
{
    vector<Point>a;
    vector<Point>p; //顺时针凸包
    vector<Point>tb;// 逆时针凸包
    void in(const int &r)
    {
        p.resize(r);  //不早凸包的时候可以把p改为a
        for(int i = 0; i < r; i++) p[i].in();
    }

    //计算多边形的周长
    double perimeter()
    {
        double sum=0;
        int n=a.size();
        for(int i=0;i<n;i++) sum+=dist(a[i],a[(i+1)%n]);
        return sum;
    }

    //计算多边形的面积
    double getArea()
    {
        int n = tb.size();  //平常的多边形就把tb换成a
        double ans=0;
        for(int i = 0; i < n; i++) ans += det(tb[i], tb[(i + 1)%n]);
        return ans / 2;
    }

    //计算多边形的重心坐标
    Point getMassCenter()
    {
        Point center(0, 0);
        if(sgn(getArea())==0) return center; //面积为0情况，当然这题说了面积不可能为0可不写
        int n = a.size();
        for(int i = 0; i < n; i++)
            center =center + (a[i] + a[(i + 1) % n]) * det(a[i], a[(i + 1) % n]);
        return center / getArea() / 6;
    }

    //计算点t是否在多边形内,返回0指在外，1指在内，2指在边界上
    int pointin(Point t)
    {
        int num=0,i,d1,d2,k,n=a.size();
        for(i=0;i<n;i++)
        {
            Line line=Line(a[i],a[(i+1)%n]);
            if(line.pointOnLine(t)) return 2;
            k=sgn(det(a[(i+1)%n]-a[i],t-a[i]));
            d1=sgn(a[i].y-t.y);
            d2=sgn(a[(i+1)%n].y-t.y);
            if(k>0&&d1<=0&&d2>0) num++;
            if(k<0&&d2<=0&&d1>0) num--;
        }
        return num!=0;
    }

    //计算多边形边界的格点数
    int border()
    {
        int num=0,i,n=a.size();
        for(i=0;i<n;i++)
            num+=gcd(abs(int(a[(i+1)%n].x-a[i].x)),abs(int(a[(i+1)%n].y-a[i].y)));
        return num;
    }

    //计算多边形内的格点数
    //Pick公式：面积=内部格点数+边界格点数/2-1
    int inside()
    {
        return int(getArea())+1-border()/2;
    }

    //判断点集是否为凸包(返回m-1==n),或者用凸包点算出凸包顶点tb(本题即是)
    void isCanHull()
    {
        sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end());
        int n = p.size();
        tb.resize(n * 2 + 5);
        int m = 0;
        for(int i = 0; i < n; i++)
        {
            while(m > 1 && sgn(det(tb[m - 1] - tb[m - 2], p[i] - tb[m - 2])) <= 0)m--;
            tb[m++] = p[i];
        }
        int k = m;
        for(int i = n - 2; i >= 0; i--)
        {
            while(m > k && sgn(det(tb[m - 1] - tb[m -2], p[i] - tb[m - 2])) <= 0)m--;
            tb[m++] = p[i];
        }
        tb.resize(m);
        if(m > 1)tb.resize(m - 1);
        //for(int i = 0; i < m - 1; i++) tb[i].out();
    }

    //判断点t(圆心)是否在凸包内部，这个是O(logn)的算法
    bool isContainOlogn(const Point &t)
    {
        int n = tb.size();
        if(n < 3)return 0;
        Point g = (tb[0] + tb[n / 3] + tb[n * 2 / 3] )/ 3.0;
        int l = 0, r = n;
        while(l + 1 < r)
        {
            int mid = (l + r) >> 1;
            int k = sgn(det(tb[l] - g, tb[mid] - g) );
            int dl = sgn(det(tb[l] - g, t - g) );
            int dr = sgn(det(tb[mid] - g, t - g) );
            if(k > 0)
            {
                if(dl >= 0 && dr < 0) r = mid;
                else l = mid;
            }
            else
            {
                if(dl < 0 && dr >= 0) l = mid;
                else r = mid;
            }
        }
        r %= n;
        int res = sgn(det(tb[l] - t, tb[r] - t));
        if(res >= 0) return true;
        return false;
    }

    //判断凸包是否惟一,若顶点之间有点说明惟一
    bool isUnique()
    {
        if(sgn(getArea()) == 0) return false;
        int n = tb.size();
        int np = p.size();
        for(int i = 0; i < n; i++)
        {
            Line line(tb[i], tb[(i + 1) % n]);
            bool isFind = false;
            for(int j = 0; j < np; j++)
            {
                if(line.pointOnLine(p[j]))
                {
                    isFind = true;
                    break;
                }
            }
            if(!isFind) return false;
        }
        return true;
    }
}poly;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        poly.in(n);
        poly.isCanHull();
        if(poly.isUnique()) puts("YES");
        else puts("NO");
    }
    return 0;
}

POJ 1228 凸包惟一性判断（多边形模板）,布布扣,bubuko.com

POJ 1228 凸包惟一性判断（多边形模板）

原文：http://blog.csdn.net/u011466175/article/details/21475611