首页 > 代码库 > poj 3348 cows 凸包面积
poj 3348 cows 凸包面积
1 /** 2 大意: 给定多个点求其确定的面积可以存放多少个面积为50的东西 3 思路: 1、凸包确定多边形 4 2、 多边形求面积 5 3、 面积/50 取整 6 **/ 7 #include <iostream> 8 #include <algorithm> 9 using namespace std; 10 #define maxn 10010 11 struct point { 12 double x,y; 13 point (double x=0,double y=0):x(x),y(y){} 14 }; 15 16 point p[maxn],ch[maxn]; 17 typedef point Vector; 18 19 Vector operator -(point a,point b){ 20 return Vector (a.x-b.x,a.y-b.y); 21 } 22 23 double cross(Vector a,Vector b){ 24 return a.x*b.y-a.y*b.x; 25 } 26 double polygonarea(point *p,int n){ 27 double area =0; 28 for(int i=1;i<n-1;i++){ 29 area += cross(p[i]-p[0],p[i+1]-p[0]); 30 } 31 return area/2; 32 } 33 bool cmp(point a,point b){ 34 if(a.x==b.x) 35 return a.y<b.y; 36 return a.x<b.x; 37 } 38 39 int convexHull(point *p,int n,point *ch){ 40 sort(p,p+n,cmp); 41 int m=0; 42 for(int i=0;i<n;i++){ 43 while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) 44 m--; 45 ch[m++] = p[i]; 46 } 47 int k = m; 48 for(int i= n-2;i>=0;i--){ 49 while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) 50 m--; 51 ch[m++] = p[i]; 52 } 53 if(n>1) m--; 54 return m; 55 } 56 int main() 57 { 58 int n; 59 cin>>n; 60 for(int i=0;i<n;i++){ 61 cin>>p[i].x>>p[i].y; 62 } 63 int res = convexHull(p,n,ch); 64 double resarea = polygonarea(ch,res); 65 cout<<(int )resarea/50<<endl; 66 return 0; 67 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。