欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Cows 【POJ 3348】【凸包+多边形面积】

程序员文章站 2024-03-16 19:58:58
...

题目链接

题目大意

给出n个点,让你求凸包的面积/50的值是多少

解题思路

先求出凸包,然后根据多边形面积公式求出公式
多边形面积公式:

    for(int i=0;i<m-1;i++)
        ans+=(ch[i].x*ch[i+1].y-ch[i+1].x*ch[i].y);
    ans=abs(ans)/2.0;

AC代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int N=1e5+5;
struct node
{
    double x,y;

    node operator - (const node &a)
    {
        node s;
        s.x=x-a.x;
        s.y=y-a.y;
        return s;
    }
};
node e[N],ch[N];
int n,m;

int cmp(node a,node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

double cross(node a,node b)
{
    return a.x*b.y-b.x*a.y;
}

void Andrew()//求凸包
{
    sort(e,e+n,cmp);
    m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&cross(ch[m-1]-ch[m-2],e[i]-ch[m-2])<=0.0)
            m--;
        ch[m++]=e[i];
    }

    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&cross(ch[m-1]-ch[m-2],e[i]-ch[m-2])<=0.0)
            m--;
        ch[m++]=e[i];
    }
}

int solve()
{
    double ans=0;
    for(int i=0;i<m-1;i++)
        ans+=(ch[i].x*ch[i+1].y-ch[i+1].x*ch[i].y);
    if(ans<0)
        ans=-ans;
    ans=0.5*ans;//ans是凸包的面积
    return (int)(ans/50.0);
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lf %lf",&e[i].x,&e[i].y);
    Andrew();
    printf("%d\n",solve());
}