UVALive6859 Points +凸包

小鱼儿 2022-07-16 12:37 78阅读 0赞

UVALive6859 Points +凸包 题目链接：[https://icpcarchive.ecs.baylor.edu/index.php?option=com\_onlinejudge&Itemid=8&page=show\_problem&problem=4871][https_icpcarchive.ecs.baylor.edu_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_4871]

题面描述：

![Center][]

![Center 1][]

题目大意：

二维平面上，给定n个点，和n个点的坐标，求解一个最小的多边形边界（边界必须是格点边界或者单位个点的对角线），使得这个多边形边界可以包含所有的点（即：所有的点都在该多边形的内部，且不能在边界上），求该多边形的周长。

题目分析：

为了使得所有的点都在多边形内，且根据多边形边界的要求，则要把每个点都进行向外扩展一个单位，并且进行凸包求解，不需要进行去重操作。需要特别注意的是：遇到不能再格点上的边，需要对其进行处理，用长边-短边，并加上短边乘以根号2即可。

代码实现：

#include <bits/stdc++.h>
    #include <cstdio>
    //#include <cstring>
    //#include <cmath>
    
    using 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;
        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);
        }
    //叉积
        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;
        }
    };
    /*
    * 求凸包，Graham算法
    * 点的编号0~n-1
    * 返回凸包结果Stack[0~top-1]为凸包的编号
    */
    const int MAXN = 500010;
    Point point[MAXN],point1[MAXN];
    int Stack[MAXN],top;
    double dist(Point a,Point b)
    {
        return sqrt((a-b)*(a-b));
    }
    //相对于list[0]的极角排序
    bool _cmp(Point p1,Point p2)
    {
        double tmp =(p1-point[0])^(p2-point[0]);
        if(sgn(tmp) > 0) return true;
        else if(sgn(tmp) == 0 && sgn(dist(p1,point[0]) - dist(p2,point[0])) <= 0)
            return true;
        else return false;
    }
    void Graham(int n)
    {
        Point p0;
        int k = 0;
        p0 = point[0];
    //找最下边的一个点
        for(int i = 1; i < n; i++)
        {
            if( (p0.y > point[i].y) || (p0.y == point[i].y && p0.x > point[i].x) )
            {
                p0 = point[i];
                k = i;
            }
        }
        swap(point[k],point[0]);
        sort(point+1,point+n,_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((point[Stack[top-1]]-point[Stack[top-2]])^(point[i]-point[Stack[top-2]])) <= 0)
                top--;
            Stack[top++] = i;
        }
    }
    
    double dis(Point a,Point b)
    {
        double xx=fabs(a.x-b.x);
        double yy=fabs(a.y-b.y);
        return fabs(xx-yy)+sqrt(2)*min(xx,yy);
    }
    
    int main()
    {
        int N;
        while(scanf("%d",&N)!=EOF)
        {
            for(int i=0; i<N; i++)
            {
                scanf("%lf%lf",&point1[i].x,&point1[i].y);
            }
            int k=0;
            for(int i=0;i<N;i++)
            {
                point[k].x=point1[i].x-1;
                point[k++].y=point1[i].y;
                point[k].x=point1[i].x+1;
                point[k++].y=point1[i].y;
                point[k].x=point1[i].x;
                point[k++].y=point1[i].y-1;
                point[k].x=point1[i].x;
                point[k++].y=point1[i].y+1;
            }
            Graham(k);
            double sum=0.0;
            for(int i=0;i<top-1;i++)
            {
                sum+=dis(point[Stack[i]],point[Stack[i+1]]);
            }
            sum+=dis(point[Stack[0]],point[Stack[top-1]]);
            printf("%.6lf\n",sum);
        }
        return 0;
    }

[https_icpcarchive.ecs.baylor.edu_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_4871]: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4871
[Center]: /images/20220716/e244d949552245378b4eeafdb81fbc55.png
[Center 1]: /images/20220716/50b81bca5b9c4d4b874ac66b87c84a11.png