凸包模板.txt

北大judue上的题吗 供学习与交流用 大家一起分享 希望能好好学习

//凸包
//按X轴主Y轴辅排序
#include<stdio.h>
int i,j,tot1,tot2,tot;
double ans,k;
int n;
int a[100010];
int x[50010],y[50010];
int cal(int a,int b,int c)
{
	int tt;
	tt=x[a]*y[b]+x[c]*y[a]+x[b]*y[c]-x[c]*y[b]-x[b]*y[a]-x[a]*y[c];
	return tt;
}//计算三角形面积，看旋转方向

/***************************快排*************************/
int qpos(int l,int r)
{
	int i,j,k1,k2,t;
	i=l-1;
	j=r+1;
	k1=x[(l+r)/2];
	k2=y[(l+r)/2];
	while (i<j)
	{
		do i++; while (x[i]<k1||(x[i]==k1&&y[i]<k2));
		do j--; while (x[j]>k1||(x[j]==k1&&y[j]>k2));
		if (i<j)
		{
			t=x[i];
			x[i]=x[j];
			x[j]=t;
			t=y[i];
			y[i]=y[j];
			y[j]=t;
		}
	}
	if (j==r) return (j-1);
	else return j;
}

int qqsort(int l,int r)
{
	int k;
	if (l<r)
	{
		k=qpos(l,r);
		qqsort(l,k);
		qqsort(k+1,r);
	}
	return 0;
}//快排 x第一要素，y第二要素
/**********************************************************************/
int main()
{
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	qqsort(1,n);
/***********************凸包**************************************/
	a[1]=1;
	a[2]=2;
	tot1=2;
	for (i=3;i<=n;i++)
	{
		while(tot1>1&&cal(a[tot1-1],a[tot1],i)<=0)
			tot1--;
		tot1++;
		a[tot1]=i;
	}
	//一条边界
	a[tot1+1]=n-1;
	tot2=tot1+1;
	for (i=n-2;i>0;i--)
	{
		while (tot2>tot1&&cal(a[tot2-1],a[tot2],i)<=0) tot2--;
		tot2++;
		a[tot2]=i;
	}//另一条边界
/*******************************************************************/
	tot=tot2-1;
	ans=0;
/************************两点距离*****************************************/
	for (i=1;i<tot;i++)
		for (j=i+1;j<=tot;j++)
		{
			k=(x[a[i]]-x[a[j]])*(x[a[i]]-x[a[j]])+(y[a[i]]-y[a[j]])*(y[a[i]]-y[a[j]]);
			if (ans<k) ans=k;
		}
/**********************************************************************/
	printf("%.0lf\n",ans);
	return 0;
}