POJ - 3348 Cows(求凸包的面积)

迈不过友情╰ 2022-06-07 06:58 188阅读 0赞

[点我看题][Link 1]

题意:一片草原上有n棵树,给出这n棵树的坐标,准备用其中的一些树围成一个多边形,每只奶牛要吃掉50m^2的草,问围成的草坪可供多少只奶牛.

分析:先求出这些树的凸包,然后求凸包的面积,最后总面积/50即为答案,求凸包的面积根据叉积就可以.

参考代码:

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    int n;
    const int maxn = 1e4+10;
    struct Point{
        int x,y;
        Point(){}
        Point( int xx, int yy)
        {
            x = xx, y = yy;
        }
        Point operator - ( const Point &p)const
        {
            return Point(x-p.x,y-p.y);
        }
        int operator ^ ( const Point &p)const
        {
            return x*p.y-p.x*y;
        }
    };
    Point p[maxn];
    int stack[maxn],top;
    
    int xmult( Point p0, Point p1, Point p2)
    {
        return (p1-p0)^(p2-p0);
    }
    
    int sqr( int x)
    {
        return x*x;
    }
    
    int dis( Point p1, Point p2)
    {
        return sqr(p1.x-p2.x)+sqr(p1.y-p2.y);
    }
    
    bool cmp( Point p1, Point p2)
    {
        int tmp = xmult(p[0],p1,p2);
        if( tmp > 0)
            return true;
        else if( tmp == 0 && dis(p[0],p1) < dis(p[0],p2))
            return true;
        else
            return false;
    }
    
    void graham( int n)
    {
        if( n == 1)
        {
            top = 0;
            stack[0] = 0;
        }
        if( n == 2)
        {
            top = 1;
            stack[0] = 0;
            stack[1] = 1;
        }
        if( n > 2)
        {
            stack[0] = 0, stack[1] = 1, top = 1;
            for( int i = 2; i < n; i++)
            {
                while( top > 0 && xmult(p[stack[top-1]],p[stack[top]],p[i]) <= 0)
                    top--;
                top++;
                stack[top] = i;
            }
        }
    }
    
    int main()
    {
        while( ~scanf("%d",&n))
        {
            Point p0;
            scanf("%d%d",&p[0].x,&p[0].y);
            p0.x = p[0].x, p0.y = p[0].y;
            int k = 0;
            for( int i = 1; i < n; i++)
            {
                scanf("%d%d",&p[i].x,&p[i].y);
                if( p0.y > p[i].y || (p0.y == p[i].y && p0.x > p[i].x))
                    p0.x = p[i].x, p0.y = p[i].y, k = i;
            }
            p[k] = p[0];
            p[0] = p0;
            sort(p+1,p+n,cmp);
    
            graham(n);
            double area = 0;
            for( int i = 1; i < top; i++)
                area += xmult(p[0],p[stack[i]],p[stack[i+1]])/2;
            printf("%d\n",int(area/50));
        }
    
        return 0;
    }

[Link 1]: http://poj.org/problem?id=3348