凸包及多边形面积

小咪咪 2022-08-10 14:41 327阅读 0赞

首先求多边形面积，这个比较简单，用的就是把一个多边形划分为多个三角形，然后求三角形面积。

代码：

double Cross(Vector A,Vector B) { return (A.x*B.y-A.y*B.x); }
    double ConvexPolygonArea(Point* p,int n)//多边形面积,，点按顺序
    {
        double area=0;
        for(int i=1;i<n-1;i++)
            area+=Cross(p[i]-p[0],p[i+1]-p[0]);
        return area/2;
    }

求凸包的算法有很多，这里给出Andrew算法。

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <queue>
    #include <vector>
    #include <map>
    #include <set>
    #include <string>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 1010;
    const double esp = 1e-10;
    struct Point
    {
        double x,y;
        Point(double x=0,double y=0):x(x),y(y) {}
    };
    typedef Point Vector;
    Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); }
    Vector operator - (Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); }
    Vector operator * (Vector A,double p) { return Vector(A.x*p,A.y*p); }
    Vector operator / (Vector A,double p) { return Vector(A.x/p,A.y/p); }
    
    bool operator < (const Point& a,const Point& b)
    {
        return a.x<b.x || (a.x==b.x && a.y<b.y);
    }
    int dcmp(double x)  //
    {
        if(fabs(x)<esp) return 0;
        else return x<0?-1:1;
    }
    bool operator == (const Point& a,const Point& b)
    {
        return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y)==0;
    }
    ///计算点积，及向量长度，及向量夹角
    double Dot(Vector A,Vector B) { return A.x*B.x+A.y*B.y; }
    double Length(Vector A) { return sqrt(Dot(A,A)); }
    double Angle(Vector A,Vector B) { return acos(Dot(A,B))/Length(A)/Length(B); }
    //计算叉积，向量逆时针旋转
    double Cross(Vector A,Vector B) { return (A.x*B.y-A.y*B.x); }
    double Area2(Vector A,Vector B,Vector C)  { return Cross(B-A,C-A); }
    Vector Rotate(Vector A,double rad)
    {
        return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
    }
    int cmp(Point a,Point b)
    {
        if(a.x!=b.x)
            return a.x<b.x;
        if(a.y!=b.y)
            return a.y<b.y;
    }
    double ConvexPolygonArea(Point* p,int n)//多边形面积,，点按顺序
    {
        double area=0;
        for(int i=1;i<n-1;i++)
            area+=Cross(p[i]-p[0],p[i+1]-p[0]);
        return area/2;
    }
    int ConvexHull(Point *p,Point *ch,int n)//求凸包
    {
        sort(p,p+n);
        int i,m=0,k;
        for(i=0;i<n;i++)
        {
            while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
            ch[m++]=p[i];
        }
        k=m;
        for(i=n-2;i>=0;i--)
        {
            while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
            ch[m++]=p[i];
        }
        if(n>1)m--;
        return m;
    }
    int main()
    {
        int n,k;
        Point a[N],ch[N];
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++)
                scanf("%lf%lf",&a[i].x,&a[i].y);
            int num=ConvexHull(a,ch,n);
            double ans=ConvexPolygonArea(ch,num);
            ans/=50.0;
            printf("%d\n",(int)ans);
        }
        return 0;
    }