poj3348 Cows 凸包+多边形面积水题

/*

poj3348 Cows 凸包+多边形面积 水题

floor向下取整，返回的是double

*/

#include<stdio.h>

#include<math.h>

#include <algorithm>

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<eps) return 1;

	return 0;

}

bool mo_gg(double x,double y)  {   return x > 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<n;++i)

    {

        while(top>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<n;++i)

	{

		ret+=mo_xmult(dian[(i+1)%n],yuan,dian[i]);

	}

	if(ret<0) ret=-ret;

	return ret/2;

}

////////

int main()

{

	int i;

	while(scanf("%d",&n)!=EOF)

	{

		for(i=0;i<n;++i)

		{

			scanf("%lf%lf",&dian[i].x,&dian[i].y);

		}

		int ret=mo_graham(n,dian,zhan);

		double area=mo_area_polygon(zhan,ret);

		printf("%.0lf\n",floor(area/50));

	}

	return 0;

}
巴特西

poj3348 Cows 凸包+多边形面积水题

最新文章

热门文章

巴特西

poj3348 Cows 凸包+多边形面积 水题

最新文章

热门文章

poj3348 Cows 凸包+多边形面积水题
