POJ 2187(凸包GrahamScan扫描+极角排序+平面最远点对）
平面最远点对
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 22454 Accepted: 6868
Description
求 N (2 <= N <= 50,000) 个点平面最远点对距离的平方.
Input
* 第1行:N
接下来每行为点的坐标 x 和 y ,(x,y)(-10,000<=x,y<=10,000的整数).
Output
输出一行，为平面最远点对距离平方.
Sample Input
4
0 0
0 1
1 1
1 0
Sample Output
2
Hint
(0, 0) a到 (1, 1) 距离平方为 2
Source
USACO 2003 Fall
凸包模版题：
先用GrahamScan扫描求凸包，显然最远点对在凸包上。
极角排序：
按照逆时针顺序给平面上的点集到一个点的距离排序，使得排序后所有点正好绕这个点一圈.（按距离远近从小到大排
思路：
GrahamScan扫描：
大致如此.
另补：
该题小Bug-有可能所有点在一条直线上。
这样也能求出：
Ex:
a序列（-1，0） （0，0) （4，0） （9，0）
则st序列重复如下操作：
（-1，1），（0，0）入队。
（4，0）入队，不左拐->（0，0）出队
队列元素<2 （4，0）入队
……
[cpp]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (50000+10)
double sqr(double x){return x*x;}
struct P
{
double x,y;
P(){}
P(double _x,double _y):x(_x),y(_y){}
}a[MAXN],st[MAXN];
int dis2(P A,P B)
{
return sqr(A.x-B.x)+sqr(A.y-B.y);
}
double dis(P A,P B)
{
return sqrt(double(dis2(A,B)));
}
struct V
{
double x,y;
V(){}
V(double _x,double _y):x(_x),y(_y){}
V(P A,P B):x(B.x-A.x),y(B.y-A.y){}
};
double operator*(V a,V b)
{
return a.x*b.y-a.y*b.x;
}
int cmp(P A,P B) //1:a>b 0:a<=b
{
double tmp=V(a[1],A)*V(a[1],B);
if (tmp>0) return 1;
else if (tmp==0) return (-(dis(a[1],A)-dis(a[1],B))>0)?1:0;
