#include<iostream>
#include<cmath>
#include<stdlib.h>
using namespace std;
#define N 50001
typedef struct
{
    int x;
    int y;
}point;
point points[N]; //点集
point sk[N];     //栈
int top; //栈顶指针

//计算两点之间距离平方
inline int dist(point a, point b)
{
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

//通过矢量叉积求极角关系（p0p1）(p0p2)
//d > 0 ,p0p1在p0p2顺时针方向上
inline int multi(point p0, point p1, point p2)    
{
	return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}


//排序函数
int cmp(const void *p, const void *q)
{
	point a = *(point *)p;
	point b = *(point *)q;
	
	int k = multi(points[0], a, b);
	if(k < 0)
		return 1; 
	else if(k == 0 && (dist(a, points[0]) - dist(b, points[0])) > 0)
		return 1;

	else
		return -1;
	
}

//互换
inline void swap(point& a, point& b)
{
	point tmp = a;
	a = b;
	b = tmp;
}

//构造凸包
void convex_hull(int n)
{
	int i, k, index = 0;
	int miny = points[index].y;
	for(i=1; i<n; i++) //找最左下顶点
	{
		if(points[i].y < miny) //找到y坐标最小的点
		{ 
			miny = points[i].y;
			index = i;
		}
		else if(points[i].y == miny && points[i].x < points[index].x) //相同的话找到x最小的
			index = i;
	}
	swap(points[0], points[index]);
	qsort(points+1, n-1, sizeof(points[0]), cmp); //p[1:n-1]按相对p[0]的极角从小到大排序

/*
for(i=0; i<n; i++)
	printf("%d %d\n", points[i].x, points[i].y);
puts("---------aa--------");
*/

	sk[0] = points[0];
	sk[1] = points[1];
	sk[2] = points[2];
	top = 2;
	for(i=3; i<n; i++)
	{
		while(multi(sk[top-1], points[i], sk[top]) > 0)
			top--;
		sk[++top] = points[i];
	}
}

int main()
{
//freopen("in.txt", "r", stdin);
	int i, j, n;
	int ans, tmp;
	while(scanf("%d", &n) != EOF)
	{
		for(i=0; i<n; i++)
			scanf("%d%d", &points[i].x, &points[i].y);
		if(n == 2)
		{
			printf("%d\n", dist(points[0], points[1]));
			continue;
		}
		convex_hull(n);

/*
for(i=0; i<=top; i++)
	printf("%d %d\n", sk[i].x, sk[i].y);
printf("------------------------\n");
*/

		ans = 0;
		for(i=0; i<top; i++)
			for(j=i+1; j<=top; j++)
			{
				tmp = dist(points[i], points[j]);
				if(tmp > ans)
					ans = tmp;
			}
		printf("%d\n", ans);
	}
	return 0;
}

• Re:Help!! get wa, why??? (60) smwwh 2010-08-29 16:19:34
• 我承认，我抄的模板（吉林大学的） 最短距离枚举凸包的顶点 (1468) hehexiaobai 2010-08-29 20:53:49
  • Orz...使用模板，过题神速 (1598) smwwh 2010-09-04 21:51:13
  • Re:我承认，我抄的模板（吉林大学的） 最短距离枚举凸包的顶点 (67) zzsx65zdf 2011-12-03 21:05:50