POJ 3348 Cows (凸包面积)

本文主要是介绍POJ 3348 Cows (凸包面积)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=3348
题意：求给定$n$个点的凸包面积除以50。

凸包板子+多边形面积板子。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
struct Point
{int x,y;Point(){}Point(int _x,int _y){x=_x;y=_y;}Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}int operator ^(const Point &b)const{return x*b.y-y*b.x;}int operator *(const Point &b) const{return x*b.x+y*b.y;}void input(){scanf("%d%d",&x,&y);}
};
//距离的平方
int dist2(Point a,Point b)
{return (a-b)*(a-b);
}
//二维凸包(int)
const int MAXN=50010;
Point list[MAXN];
int Stack[MAXN],top;
//相对于list[0]进行极角排序
bool _cmp(Point p1,Point p2)
{double tmp=(p1-list[0])^(p2-list[0]);if(tmp>0)return true;else if(tmp==0&&dist2(p1,list[0])<=dist2(p2,list[0]))return true;else return false;
}
void Graham(int n)
{Point p0;int k=0;p0=list[0];//找最左下的点for(int i=1;i<n;i++){if((p0.y>list[i].y)||(p0.y==list[i].y&&p0.x>list[i].x)){p0=list[i];k=i;}}swap(list[k],list[0]);sort(list+1,list+n,_cmp);if(n==1){top=1;Stack[0]=0;return ;}if(n==2){top=2;Stack[0]=0;Stack[1]=1;return ;}Stack[0]=0;Stack[1]=1;top=2;for(int i=2;i<n;i++){while(top>1&&((list[Stack[top-1]]-list[Stack[top-2]])^(list[i]-list[Stack[top-2]]))<=0)top--;Stack[top++]=i;}
}
int CalcArea(Point p[],int n)
{int res=0;for(int i=0;i<n;i++)res+=(p[i]^p[(i+1)%n])/2;return res;
}
Point p[MAXN];
int main()
{int n;scanf("%d",&n);for(int i=0;i<n;i++)list[i].input();Graham(n);for(int i=0;i<top;i++)p[i]=list[Stack[i]];printf("%d",CalcArea(p,top)/50);return 0;
}

这篇关于POJ 3348 Cows (凸包面积)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---