poj 2187（凸包）

Beauty Contest

Time Limit: 3000MS	Memory Limit: 65536K
Total Submissions: 32975	Accepted: 10232

Description

Bessie, Farmer John's prize cow, has just won first place in a bovine beauty contest, earning the title 'Miss Cow World'. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range -10,000 ... 10,000. No two farms share the same pair of coordinates. 

Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms. 

Input

* Line 1: A single integer, N 

* Lines 2..N+1: Two space-separated integers x and y specifying coordinate of each farm 

Output

* Line 1: A single integer that is the squared distance between the pair of farms that are farthest apart from each other. 

Sample Input

4
0 0
0 1
1 1
1 0
      

Sample Output

2
      

Hint

Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of 2) 

題目大意：

求所有點中距離最遠的兩點的距離。

解題思路：

距離最遠的兩點一定是在凸包上，是以先求出凸包，時間複雜度為O(nlogn)

用Graham掃描法求出凸包

http://www.cnblogs.com/jbelial/archive/2011/08/05/2128625.html

Graham算法中有關叉積的應用

http://www.cnblogs.com/codingmylife/archive/2012/09/18/2690401.html

之後在凸包上求出最大的兩點距離，用暴力枚舉的話時間複雜度為O(n^2)可能會逾時，是以選擇用旋轉卡殼算法，時間複雜度為O(n)。

旋轉卡殼算法

http://www.cnblogs.com/xdruid/archive/2012/07/01/2572303.html

最後的總時間複雜度為O(nlogn)

代碼如下：

#include<iostream> 
#include<stdio.h> 
#include<math.h> 
#include<string.h> 
#include<vector> 
#include<queue> 
#include<map> 
#include<stack> 
#include<queue> 
#include<algorithm> 
using namespace std; 
const int MAX=0x7fffffff; 
int min(int a,int b) 
{ 
    if(a<b)return a; 
    else return b; 
} 
int max(int a,int b) 
{ 
    if(a>b)return a; 
    else return b; 
}
int n;

struct point
{
	int x,y,flag;
	double an;
};
point p[5000005];
int len(int x1,int y1,int x2,int y2)
{
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
bool cmp(point a,point b)
{
	if(a.y<b.y||(a.y==b.y&&a.x<b.x))return true;
	return false;
}
int jud(point p1,point p2,point p3)
{
	return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
int tubao()
{
	vector<int>v;
	v.push_back(0);
	v.push_back(1);
	//Graham掃描法
	for(int i=2;i<n;i++)//對所有點掃兩遍，就可以不用對所有點按極角排序
	{
			while(jud(p[v[v.size()-2]],p[v[v.size()-1]],p[i])<=0&&v.size()>=2)
			{
				v.pop_back();
			}
			v.push_back(i);
	}
	int pos=v.size();
	for(int i=n-2;i>0;i--)
	{
		while(v.size()>pos&&jud(p[v[v.size()-2]],p[v[v.size()-1]],p[i])<=0)
			v.pop_back();
		v.push_back(i);
	}
	int sum=len(p[0].x,p[0].y,p[1].x,p[1].y);
	int top=v.size()-1,q=1;
	for(int i=0;i<top;i++)//旋轉卡殼
	{
		while(abs(jud(p[v[(i+1)%top]],p[v[i%top]],p[v[q%top]]))<abs(jud(p[v[(i+1)%top]],p[v[i%top]],p[v[(q+1)%top]])))
			q=(q+1)%top;
		sum=max(sum,max(len(p[v[i%top]].x,p[v[i%top]].y,p[v[q%top]].x,p[v[q%top]].y),len(p[v[(i+1)%top]].x,p[v[(i+1)%top]].y,p[v[q%top]].x,p[v[q%top]].y)));
	}
	return sum;
}

int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&p[i].x,&p[i].y);
		}
		if(n==2)
		{
			printf("%d\n",len(p[0].x,p[0].y,p[1].x,p[1].y));
			continue;
		}
		sort(p,p+n,cmp);//對所有點按y由小到大排序，如果y相等按x由小到大排序
		printf("%d\n",tubao());
	}
	return 0;
}