2187.c

poj2187给一堆点,求出其中的最远点对,凸包的应用

#include <stdio.h>
#define MAXN 50000
typedef struct point
{
	int x,y;
}point;
int hull[MAXN];
point p[MAXN];
int n;
int ans;

void init()
{
	int i;

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

point toVector(int p1,int p2)
{
	point temp;

	temp.x=p[p2].x-p[p1].x;
	temp.y=p[p2].y-p[p1].y;
	return temp;
}

int cross(point a,point b)
{
	return a.x*b.y-a.y*b.x;
}

int turn(int p1,int p2,int p3)
{
	int temp;
	temp=cross(toVector(p1,p2),toVector(p2,p3));
	if (temp>0) return 1;
	else return 0;
}

int cmp(point a,point b)
{
	if (a.x<b.x) return 1;
	else if (a.x==b.x)
	{
		if (a.y<b.y) return 1;
	}
	return 0;
}

void myqsort(int l,int r)
{
	point mid,temp;
	int i,j;

	i=l;
	j=r;
	mid=p[(i+j)>>1];
	while (i<=j)
	{
		while (cmp(p[i],mid)) i++;
		while (cmp(mid,p[j])) j--;
		if (i<=j)
		{
			temp=p[i];
			p[i]=p[j];
			p[j]=temp;
			i++; j--;
		}
	}
	if (l<j) myqsort(l,j);
	if (i<r) myqsort(i,r);
}

void convexHull()
{
	int stack[MAXN];
	int top,i;
	
	stack[0]=0;
	stack[1]=1;
	top=2;
	for (i=2 ;i<n ;i++)
	{
		while (top>1 && turn(stack[top-2],stack[top-1],i)==0) top--;
		stack[top++]=i;
	}
	for (i=0 ;i<top ;i++) hull[i+1]=stack[i];
	hull[0]=top;
	stack[0]=n-1;
	stack[1]=n-2;
	top=2;
	for (i=n-3 ;i>0 ;i--)
	{
		while (top>1 && turn(stack[top-2],stack[top-1],i)==0) top--;
		stack[top++]=i;
	}
	for (i=0 ;i<top ;i++) hull[i+hull[0]]=stack[i];
	hull[0]+=top-1;
}

int getLen(point a,point b)
{
	return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void getMax()
{
	int i,j;
	int t;

	ans=0;
	for (i=1 ;i<hull[0] ;i++)
	{
		for (j=i+1 ;j<=hull[0] ;j++)
		{
			t=getLen(p[hull[i]],p[hull[j]]);
			if (t>ans) ans=t;
		}
	}
}

void work()
{
	int i;
	myqsort(0,n-1);
	convexHull();
	getMax();
	printf("%d\n",ans);
}

main()
{
//	freopen("0.txt","r",stdin);
	init();
	work();
}