4317150_ac_344ms_1016k.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# define INF 100000

struct dian
{
	long x,y;
};
struct dian p[100000],z[10000];	
long n,tail,x,y,pos[10000];
double s[100000],m;



int cmp(const void * a,const void * b)
{
	struct dian *aa,*bb;
	long i,j,u,v;

	aa=(struct dian *) a;
	bb=(struct dian *) b;
	i=aa->x-x;
	j=aa->y-y;
	u=bb->x-x;
	v=bb->y-y;
	if (i*v-j*u>0) return (-1);
	else if (i*v-j*u<0) return(1);
	else if (i*i+j*j<u*u+v*v) return (-1);
	else return (1);
}

double find(struct dian d,long s,long e)
{
	long i,j,a,b,k,t=-1,kk=0;
	struct dian zz[100];
	double mj=0;
	
	k=s;
	while (k<=e && kk<2)
	{
		if (p[k].x!=d.x || p[k].y!=d.y) {zz[++t]=p[k]; kk++;}
		k++;
	}
	for (; k<=e; k++)
	{
		if (p[k].x==d.x && p[k].y==d.y) continue;
		do
		{	
			i=p[k].x-zz[t].x;
			j=p[k].y-zz[t].y;
			a=zz[t-1].x-zz[t].x;
			b=zz[t-1].y-zz[t].y;
			if (i*b-j*a<=0) t--;
		}while (i*b-j*a<=0 && t>0);
		zz[++t]=p[k];
	}
	for (k=0; k<t; k++)
		mj+=((zz[k].x-x)*(zz[k+1].y-y)-(zz[k].y-y)*(zz[k+1].x-x))*1.0/2;
	return (mj);
}

void tubao()
{
	long k,i,j,a,b;
	
	qsort(p,n,sizeof(p[0]),cmp);		
	tail=-1;
	for (k=0; k<2; k++)
	{
		z[++tail]=p[k];
		pos[tail]=k;
	}
	for (k=2; k<n; k++)
	{
		do
		{
			i=p[k].x-z[tail].x;
			j=p[k].y-z[tail].y;
			a=z[tail-1].x-z[tail].x;
			b=z[tail-1].y-z[tail].y;
			if (i*b-j*a<=0) tail--;
		}while (i*b-j*a<=0 && tail>0);
		z[++tail]=p[k];
		pos[tail]=k;
	}		
	m=0;
	for (k=0; k<tail; k++)
	{
		s[k]=((z[k].x-x)*(z[k+1].y-y)-(z[k+1].x-x)*(z[k].y-y))*1.0/2;
		m+=s[k];
	}
}

int main()
{
	long k;
	double min,ss;

	scanf("%d",&n);
	while (n!=0)
	{
		x=INF; 
		y=INF;
		for (k=0; k<n; k++)
		{
			scanf("%ld%ld",&p[k].x,&p[k].y);
			if (p[k].y<y || p[k].y==y && p[k].x<x)
			{
				x=p[k].x;
				y=p[k].y;
			}
		}
		tubao();
		s[tail]=0;			
		min=m;
		for (k=1; k<tail; k++)
		{
			ss=m-s[k]-s[k-1]+find(z[k],pos[k-1],pos[k+1]);
			if (ss<min) min=ss;
		}
		ss=m-s[tail-1]+find(z[tail],pos[tail-1],n-1);
		if (ss<min) min=ss;		
		x=INF;
		y=INF;
		n--;
		for (k=0; k<n; k++)
		{
			p[k]=p[k+1];
			if (p[k].y<y || p[k].y==y && p[k].x<x)
			{
				x=p[k].x;
				y=p[k].y;
			}
		}
		qsort(p,n,sizeof(p[0]),cmp);
		tubao();
		if (m<min) min=m;
		printf("%.2lf\n",min);
		scanf("%d",&n);
	}
	return 0;
}