pku 3348 凸包（化简）.txt

ACM资料大集合

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

#define NMAX 5555
#define MAX 99999999
#define PI 3.1415926

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

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_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;
}

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;miny=shuru[i].y;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&&get_cj(tubao[s],chuli[i],tubao[s-1])<=0)
			s--;
		tubao[++s]=chuli[i];//满足凸包条件，或栈只剩一个点时
		i=get_next(i,rnum);
	}
	while(!((chuli[i].x==tubao[1].x)&&(chuli[i].y==tubao[1].y)));//循环一圈
	//最后一个点是否在凸包上，还要再判断（这个不确定）	
	while(s>=3&&get_cj(tubao[s],chuli[i],tubao[s-1])<=0) 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;
       }
    tbnum=create_tubao(num);
//   print(tbnum);
    cout<<(int)((areas(tbnum))/50)<<endl;
    }
	return 0;
}


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

#define NMAX 5555
#define MAX 99999999
#define PI 3.1415926

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

point tubao[NMAX];
point shuru[NMAX];
point chuli[NMAX];
point temp[NMAX];
point zx;


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


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

int next(int i,int tbnum)
{
	if(i==tbnum) return 1;
	else return i+1;
}
double areas(int tbnum)
{
	int i;
	double s=0;
	for(i=1;i<=tbnum;i++) s+=area(tubao[i],tubao[next(i,tbnum)]);
	return s/2;
}

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

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

int cmpcj(const void *a,const void *b)
{
	double xx=get_cj((*(point *)b), (*(point *)a), zx), yy;
	if(xx==0) 
	{
		yy=get_dis((*(point *)a),zx)-get_dis((*(point *)b),zx);
		return (int)yy;
	}
	return (int)xx;
}

int get_xulie(int num)
{
	int i,j;
	for(i=1;i<=num;i++)	temp[i]=shuru[i];
//	printf("%.2f %.2f\n",zx.x,zx.y);
	qsort(temp+1,num,sizeof(temp[1]),cmpcj);
//	printf("qsort\n");
//	system("pause");
	chuli[1]=temp[1];
	for(i=2,j=1;i<=num;i++)
	{
		if(!(temp[i].x==temp[i-1].x && temp[i-1].y == temp[i].y)) chuli[++j]=temp[i];
	}
	return j;	
}

void print_xl(int ttnum)
{
	 int i;
     for(i=1;i<=ttnum;i++)
      printf("%.2f  %.2f\n",chuli[i].x,chuli[i].y);
}
int create_tubao(int num)
{
	int tbnum,ttnum,s,i;
	double minx,miny;
	minx=shuru[1].x;miny=shuru[1].y;
	for(i=2;i<=num;i++)
	{
		if(minx>shuru[i].x)
		{
			minx=shuru[i].x;miny=shuru[i].y;
			zx=shuru[i];
		}
		else if(minx==shuru[i].x && miny>shuru[i].y)
		{
			miny=shuru[i].y;
			zx=shuru[i];
		}
	}
	ttnum=get_xulie(num);
//  print_xl(ttnum);
//	system("pause");
	tubao[1]=chuli[1];
	tubao[2]=chuli[2];
	s=2;
	for(i=3;i<=ttnum;i++)
	{
//		printf("tbs=%.2f %.2f tbs-1=%.2f %.2f cj=%.2f\n",tubao[s].x,tubao[s].y,tubao[s-1].x,tubao[s-1].y,get_cj(tubao[s],chuli[i],tubao[s-1]));
		while(s>=2 && get_cj(tubao[s],chuli[i],tubao[s-1])<=0) s--;
		tubao[++s]=chuli[i];
//		printf("s=%d chuli[i]=%.2f %.2f\n",s,chuli[i].x,chuli[i].y);
//		print(s);
	}
	while(s>=3 && get_cj(tubao[s],chuli[1],tubao[s-1])<=0) s--;
	return s;
}

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;
       }
 	   tbnum=create_tubao(num);
// 	  print(tbnum);
    cout<<(int)((areas(tbnum))/50)<<endl;
    }
	return 0;
}