pku 3348 凸包（未化简）.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
using namespace std;

#define NMAX 10005
#define MAX 99999999
#define PI 3.1415926

typedef struct point
{
 double x;
 double y;
}point;

/*
typedef struct vec
{
	double x;
	double y;
	double len;
}vec;
*/
point tubao[NMAX];
point shuru[NMAX];
point chuli[NMAX];
point temp[NMAX];
point zx;

double area(point a,point b)
{  return a.x*b.y-a.y*b.x;}

double areas(int tbnum)
{//求 n 个点 的面积   A中的点按逆时针方向存放 
  //多边形是任意的凸或凹多边形，
   double re=0;
   int i;
   if(tbnum<3)return 0;
   for(i=0;i<tbnum;i++)
      re+=area(tubao[i+1],tubao[(i+1)%tbnum+1]);
   re=fabs(re/2);
   return re;
}

double get_cj(point a,point b,point o)
{//结果大于0，b在o-〉a的逆时针方向
	return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
/*
double get_dj(vec a,vec b)
{//向量a,b的点积
	return a.x*b.x+a.y*b.y;
}
*/
/*
double get_qj(vec a)
{	//这个函数不用，因为atan的计算不精确
	if(a.x==0&&a.y>0) return PI/2;
	else if(a.x==0 && a.y<0) return 3*PI/2;
	else if(a.x<0) return atan(a.y/a.x)+PI;
	else if(a.x>0&&a.y<0) return atan(a.y/a.x)+2*PI;
	else return atan(a.y/a.x);
}
*/
double get_dis(point a,point b)
{
	return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
bool cmqj(point a,point b)
{
	double cj;
	cj=get_cj(a,b,zx);
	if(cj>0) return true;
	else if(cj==0&&get_dis(zx,a)<get_dis(zx,b)) return true;
	else return false;

//比较a,b关于水平线的倾角
//	point o;
//	vec oa,ob;
//	//点o是多边形任意三个点所围成三角形的重心，这个点必在凸包内
//	o.x=(shuru[1].x+shuru[2].x+shuru[3].x)/3;
//	o.y=(shuru[1].y+shuru[2].y+shuru[3].y)/3;
//	//o->s是水平方向长度为1的向量
//	oa.x=a.x-o.x; oa.y=a.y-o.y; oa.len=sqrt(pow(a.x-o.x,2)+pow(a.y-o.y,2)); 
//	ob.x=b.x-o.x; ob.y=b.y-o.y; ob.len=sqrt(pow(b.x-o.x,2)+pow(b.y-o.y,2)); 
//	return get_qj(oa)<get_qj(ob);
}

bool cmfx(point mm,point o,point e)
{//判断点mm是不是在向量o->e的左侧(即逆时针方向)
	if(get_cj(e,mm,o)>0) return true;
//	if(get_cj(o,e,mm)>0) return true;
	else return false;
//	double a,b,c;
//	a=e.y-o.y;b=o.x-e.x;c=o.x*e.y-o.y*e.x;
//	if(mm.x*a+b*mm.y<c) return true;
//	else if(mm.x*a+b*mm.y==c && get_dis(o,e) > get_dis(o,mm)) return true; 
//	else return false;
}

int get_next(int now,int num)
{
	if(now==num) return 1;
	else return now+1;
}

void print_chuli(int num)
{
	  int i;
	  cout<<"this is chuli"<<endl;
     for(i=1;i<=num;i++)
      printf("%.2f  %.2f\n",chuli[i].x,chuli[i].y);
	 cout<<"end"<<endl;
}
int create_xulie(int num)
{
	int i,j;
	point temp[NMAX];
	for(i=1;i<=num;i++) temp[i]=shuru[i];
	sort(temp+1,temp+1+num,cmqj);
	chuli[1]=temp[1];
	j=1;
	for(i=2;i<=num;i++)
	{
		if(!(temp[i].x==temp[i-1].x &&temp[i].y==temp[i-1].y)) chuli[++j]=temp[i];
	}
//	print_chuli(j);
	return j;
}

int create_tubao(int num)
{
	//scan算法求凸包，O(nlogn)
	int minnum,rnum;
	int i,s;
	double minx,miny;
	minx=MAX;
	miny=MAX;
	for(i=1;i<=num;i++)
	{	
		if(shuru[i].x<minx) {minx=shuru[i].x;minnum=i;}
		else if(shuru[i].x==minx&&shuru[i].y<miny) {miny=shuru[i].y;minnum=i;}
	}
	zx=shuru[minnum];//zx是最左边的点（如有很多个，则是最下角的那个）
	rnum=create_xulie(num);
	tubao[1]=chuli[1];
	tubao[2]=chuli[2];
	s=2;//栈顶位置
	i=get_next(2,rnum);
	do
	{
		//注意s>=2，这样栈最多退到只剩一个点 
		while(s>=2&&cmfx(chuli[i],tubao[s-1],tubao[s])==false)
			s--;
		tubao[++s]=chuli[i];//满足凸包条件，或栈只剩一个点时
		i=get_next(i,rnum);
	}
	while(!((chuli[i].x==tubao[1].x)&&(chuli[i].y==tubao[1].y)));//循环一圈
	//最后一个点是否在凸包上，还要再判断
	if(cmfx(chuli[i],tubao[s-1],tubao[s])==false) s--;
	return s;
}

void print(int tbnum)
{
     int i;
     for(i=1;i<=tbnum;i++)
      printf("%.2f  %.2f\n",tubao[i].x,tubao[i].y);
}

int main()
{
    int i,num,tbnum,fa,fb;
    while(scanf("%d",&num)!=EOF)
    {
    for(i=1;i<=num;i++)
       {
         cin>>shuru[i].x>>shuru[i].y;
//       scanf("%f %f",&fa,&fb);
//       shuru[i].x=fa;shuru[i].y=fb;
//     scanf("%f%f",&shuru[i].x,&shuru[i].y);
       }
    tbnum=create_tubao(num);
//    print(tbnum);
    cout<<(int)((areas(tbnum))/50)<<endl;
    }
	return 0;
//    cin>>i;
}