2079.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"stdio.h"
#include<algorithm>
//ifstream in("triangle.in");
//#define cin in

using namespace std;

/////////////////////////
#define Type long /*坐标类型*/
/////////////////////////


struct point
{Type x,y;
point(){x=y=0;}
point(Type &x,Type &y):x(x),y(y){;}
bool operator==(point &a){return x==a.x&&y==a.y;}
};

int cmp_x_y(point a,point b)
{return a.y<b.y||(a.y==b.y&&a.x<b.x);}

void sort(point *a,int n)
{sort(&a[0],&a[n],cmp_x_y);}




const double pi=3.14159265359;

inline Type cheng(point a,point b,point c)
{
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}




//n*log(n)
//求凸包,返回凸包上的点的个数，wall:凸包顶点数组

//p按坐标排序先!!!

int convex(point *p,int n,point *wall)
{int i;int st;Type h;
int stack[50011],sign[50011];

st=0;
stack[st++]=0;
stack[st++]=1;

for(i=0;i<n;i++)sign[i]=0;

sign[1]=1;
i=2;

while(i<n)
{while(st>=2&&(h=cheng(p[stack[st-1]],p[stack[st-2]],p[i]))/**/ >= /**/ 0)
//在凸包边上也算，use '>'
{st--;if(h)sign[stack[st]]=0;}
stack[st++]=i;sign[i]=1;i++;
}

i--;

while(i>=0)
{while(sign[i])i--;

while(st>=2&&cheng(p[stack[st-1]],p[stack[st-2]],p[i])/**/ >= /**/ 0)st--;

stack[st++]=i;
i--;
}

st--;

if(wall){for(i=0;i<st;i++)wall[i]=p[stack[i]];}

return st;
}


point wall[50010];
point p[50010];
long n,s;

inline long ab(long a)
{
	return a>0?a:-a;
}

int main()
{
	long i,j,l;long k,h;
	while(1)
	{
		//cin>>n;
		scanf("%ld",&n);
		if(n<0)break;

		for(i=0;i<n;i++)
		{
			//cin>>p[i].x>>p[i].y;
			scanf("%ld%ld",&p[i].x,&p[i].y);
		}

		sort(p,n);
		if(n>3)n=convex(p,n,wall);
		else for(i=0;i<n;i++)wall[i]=p[i];

		s=cheng(wall[0],wall[1],wall[2]);
		s=s>0?s:-s;
		
		for(l=1,i=3;i<n;i++)
		{
			k=0;
			for(j=l;j<i;j++)
			{
				h=ab(cheng(wall[i],wall[j],wall[k]) );
				while(k<j-1&&(h=ab(cheng(wall[i],wall[j],wall[k]) ))<ab(cheng(wall[i],wall[j],wall[k+1])) )
					k++;
				if(h>s)
				{
					s=h;
					l=j;
				}
			}
		}


		printf("%.2lf\n",(double)s/2);
	}
	return 0;
}