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());
}