/*poj3348 Cows 凸包+多边形面积 水题floor向下取整,返回的是double*/#include #include #include using namespace std;const double eps = 1e-8; struct point{ double x,y;};int n;point dian[10000+10],zhan[10000+10];//point *mo_dian;double mo_distance(point p1,point p2){ return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}double mo_xmult(point p2,point p0,point p1)//p1在p2左返回负,在右边返回正{ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}bool mo_ee(double x,double y){ double ret=x-y; if(ret<0) ret=-ret; if(ret y + eps;} // x > y bool mo_ll(double x,double y) { return x < y - eps;} // x < y bool mo_ge(double x,double y) { return x > y - eps;} // x >= y bool mo_le(double x,double y) { return x < y + eps;} // x <= y bool mo_cmp(point a,point b) // 第一次排序 { if( mo_ee(a.y ,b.y ) ) return mo_ll(a.x, b.x); return mo_ll(a.y,b.y); } bool mo_cmp1(point a,point b) // 第二次排序 { double len = mo_xmult(b,mo_dian[0],a); if( mo_ee(len,0.0) ) return mo_ll(mo_distance(mo_dian[0],a),mo_distance(mo_dian[0],b)); return mo_gg(len,0.0); } int mo_graham(int n,point *dian,point *stk){ int i,top=1; mo_dian=dian; sort(mo_dian,mo_dian+n,mo_cmp); sort(mo_dian+1,mo_dian+n,mo_cmp1); stk[0]=mo_dian[0]; stk[1]=mo_dian[1]; for(i=2;i 0&&mo_xmult(mo_dian[i],stk[top-1],stk[top])<=0) --top; stk[++top]=mo_dian[i]; } return top+1; }double mo_area_polygon(point *dian,int n){ int i; point yuan; yuan.x=yuan.y=0; double ret=0; for(i=0;i