NYOJ-78-圈水池

忘是亡心i 2022-04-24 09:32 155阅读 0赞

题目衔接：[http://acm.nyist.cf/problem/78][http_acm.nyist.cf_problem_78]

> # 圈水池 #
> 
> 有一个牧场，牧场上有很多个供水装置，现在牧场的主人想要用篱笆把这些供水装置圈起来，以防止不是自己的牲畜来喝水，各个水池都标有各自的坐标，现在要你写一个程序利用最短的篱笆将这些供水装置圈起来！（篱笆足够多，并且长度可变）
> 
> ## 输入描述: ##
> 
>     第一行输入的是N,代表用N组测试数据（1<=N<=10）
>     第二行输入的是m,代表本组测试数据共有m个供水装置（3<=m<=100）
>     接下来m行代表的是各个供水装置的横纵坐标
> 
> ## 输出描述: ##
> 
>     输出各个篱笆经过各个供水装置的坐标点，并且按照x轴坐标值从小到大输出，如果x轴坐标值相同，再安照y轴坐标值从小到大输出

> ## 样例输入:   1   4   0 0   1 1   2 3   3 0 ##
> 
> ## 样例输出: ##
> 
>     0 0
>     2 3
>     3 0

大意：。。。

思路：凸包水题，使用Graham算法完后，在将点存进另一个数组排序输出即可

/*
    题目大意:。。。
    
    思路：凸包水题
    
    */
    #include<map>
    #include<set>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include <vector>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    #define Test() {freopen("F:\\test.in","r",stdin);freopen("F:\\test1.out","w",stdout);}
    const int maxn=2e4+10;
    const double pi=acos(-1.0);
    const int N=110;
    const ll mod=1e9+7;
    struct point
    {
        int x,y;
    } p[maxn],pp[maxn];
    int Stack[maxn],top;
    int sign(double x)
    {
        if(fabs(x)<esp)
            return 0;
        if(x<0)
            return -1;
        else
            return 1;
    }
    ///距离
    double dis(point a,point b)
    {
        return sqrt((double)pow((a.x-b.x),2)+pow((a.y-b.y),2));
    }
    ///叉积
    int mulit(point a,point b,point c)
    {
        return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    }
    ///极角排序：按照该点与x轴的夹角进行逆时针比较
    bool cmp(point a,point b)
    {
        int temp=mulit(p[0],a,b);
        if(temp>0)
            return true;
        if(temp==0&&dis(p[0],a)<dis(p[0],b))
            return true;
        return false;
    }
    ///凸包
    void tb(int n)
    {
        point p0;
        int k;
        p0=p[0];
        for(int i=1; i<n; i++)
        {
            if(p0.y>p[i].y||(p0.y==p[i].y&&p0.x>p[i].x))
            {
                p0=p[i];
                k=i;
            }
        }
        p[k]=p[0];
        p[0]=p0;
        sort(p+1,p+n,cmp);
        if(n==1)
        {
            top=0;
            Stack[0]=0;
            return ;
        }
        if(n==2)
        {
            top=1;
            Stack[0]=0;
            Stack[1]=1;
            return ;
        }
        if(n>2)
        {
            for(int i=0; i<=1; i++)
                Stack[i]=i;
            top=1;
            for(int i=2; i<n; i++)
            {
                while(top>0&&mulit(p[Stack[top-1]],p[Stack[top]],p[i])<=0)
                    top--;
                top++;
                Stack[top]=i;
            }
        }
    }
    
    bool cmp1(point a,point b)
    {
        if(a.x==b.x)
            return a.y<b.y;
        return a.x<b.x;
    }
    int main()
    {
    
        T()
        {
            int n;
            scanf("%d",&n);
            for(int i=0; i<n; i++)
                cin>>p[i].x>>p[i].y;
            if(n==1)
            {
                printf("0.00\n");
                continue;
            }
            if(n==2)
            {
                printf("%.2lf\n",dis(p[0],p[1]));
                continue;
            }
            tb(n);
            for(int i=0; i<=top; i++)
            {
                pp[i]=p[Stack[i]];
            }
            sort(pp,pp+top+1,cmp1);
            for(int i=0;i<=top;i++)
                printf("%d %d\n",pp[i].x,pp[i].y);
        }
        return 0;
    }

[http_acm.nyist.cf_problem_78]: http://acm.nyist.cf/problem/78