2187.txt

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

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

////////////////////////////////
typedef int Type;/*????????*/
////////////////////////////////

//????????
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;}
};
//????
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);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}

//????
inline Type dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
inline Type dcheng(point b,point c)
{return b.x*c.x+c.y*b.y;}

//??????????
int dis(point a,point b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.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);}


////////////////////////////////////////////////////////////
//O(n*log(n))
//??????,??????????????????????wall:????????????
//security

//p????????????!!!

const long convex_size=50010;
int stack[convex_size],sign[convex_size];

int convex(point *p,int n,point *wall)
{
	int i;int st;Type h;

	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 '>';	??????????????????????||n<3,??????'>'??????????
		{
			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 p[50010], pt[50010];
int n;


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

int main()
{
	int i, j;
	int temp, best;
	point a, b;

	scanf( "%d", &n );

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

	sort( pt, n );

	n = convex( pt, n, p );
	
	best = 0;
	for( i=0; i<n; i++ )
	for( j=i+1; j<n; j++ )
		if( ( temp = dis( p[i], p[j] ) ) > best )
			best = temp;

	printf( "%d\n", best );

	return 0;
}