#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define PI 3.14159265

struct point
{
	double x, y, angel;
}p[50005], ch[50005];

double dist (point a, point b)
{
	return sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double multi (point a, point b, point c)//差乘 
{
	double x1, y1, x2, y2;
	x1 = b.x - a.x;
	y1 = b.y - a.y;
	x2 = c.x - b.x;
	y2 = c.y - b.y;
	return x1*y2 - x2*y1;
}

bool cmp (point a, point b)
{
	if (a.y == b.y)
		return a.x < b.x;
	return a.y < b.y;
}

bool cmp2 (point a, point b)
{
	if (a.angel == b.angel)
	{
		if (a.x == b.x)
			return a.y > b.y;
		return a.x > b.x;
	}
	return a.angel < b.angel;
}

int main()
{
	int n, i, top,tp1,tp2;
	double r, len=-1.0;
	
	while (scanf ("%d", &n)!=EOF)
	{
		for (i = 0; i < n; i++)
			scanf ("%lf%lf", &p[i].x, &p[i].y);
		sort (p, p+n, cmp);    //找到左下角的p[0]

		//找相对于p[0]的极角，并把除了p[0]以外的点按照极角排序
		for (i = 1; i < n; i++)
			p[i].angel = atan2 (p[i].y-p[0].y, p[i].x-p[0].x);
		sort (p+1, p+n, cmp2);

		//Graham_Scan算法
		ch[0] = p[0], ch[1] = p[1], ch[2] = p[2];
		top = 3;
		for (i = 3; i < n; i++)
		{
			while (top > 2 && multi (ch[top-2], ch[top-1], p[i]) <= 0)
				top--;
			ch[top++] = p[i];
		}
		
		for(i=0;i<top;i++)
		    for(int j=i+1;j<top;j++)
		    {
				double tis=dist(ch[i],ch[j]);
				if(tis>len)
				{
					tp1=i;tp2=j;
					len=tis;
				}
			}
		len=(ch[tp1].x-ch[tp2].x)*(ch[tp1].x-ch[tp2].x) + (ch[tp1].y-ch[tp2].y)*(ch[tp1].y-ch[tp2].y);
		int sp=(int)len;
		printf ("%d\n",sp);
	}
	system("pause"); 
	return 0;
}

• 这也可以过？ (119) ProgrammingEveryday 2012-08-21 03:15:09