水平序 Graham 扫描算法：
计算二维凸包的时候可以用到，Graham 扫描算法有水平序和极角序两种。
极角序算法能一次确定整个凸包，
但是计算极角需要用到三角函数，速度较慢，精度较差，特殊情况较多。
水平序算法需要扫描两次，但排序简单，讨论简单，不易出错。
【算法流程】
1.对顶点按x为第一关键字，y为第二关键字进行排序。
2.准备一个空栈，并将前两个点压入栈。
3.对于每一个顶点A，只要栈顶中还至少两个顶点，记栈顶为T，栈中第二个为U。
若UT（向量） * TA（向量） <= 0， 则将T弹出。重复此过程。
4.直到上一步不再弹出顶点，将A压入栈。扫描完一遍之后得到凸包的下凸壳。
5.将点集倒过来再进行一次，得到凸包的上凸壳，组合起来即可。
【算法的时间复杂度】
算法的瓶颈在排序，所以时间复杂度是 O(N log N)。 若坐标均为整数，可以用基数排序将复杂度优化到 O(N)。
贴上代码了～：
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define ll long long
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
using namespace std; const int INF = 0x3f3f3f3f;
const int MAXN = ;
const double eps = 1e-; struct POINT{
int x;
int y;
POINT() : x(), y() {};
POINT(double _x_, double _y_) : x(_x_), y(_y_) {};
}; bool operator < (const POINT & l, const POINT & r){
return l.y < r. y || (l.y == r.y && l.x < r.x);
} int Cross(const POINT & a, const POINT & b, const POINT & o){
return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
} int SquareDis(POINT a, POINT b){
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
} int Graham(POINT *pnt, POINT *res, int n){
int i, len, top =;
sort(pnt, pnt + n);
if (n == )
return ;
res[] = pnt[];
if (n == )
return ;
res[] = pnt[];
if (n == )
return ;
res[] = pnt[];
for (i =; i < n; i++){
while (top && Cross(pnt[i], res[top], res[top -]) >= )
top--;
res[++top] = pnt[i];
}
len = top;
res[++top] = pnt[n -];
for (i = n -; i >=; i--){
while (top != len && Cross(pnt[i], res[top], res[top -]) >= )
top--;
res[++top] = pnt[i];
}
return top;
} int rotating_calipers(POINT *ch, int n){
int q =, ans =;
ch[n] = ch[];
for (int i = ; i < n; ++i){
while (Cross(ch[i + ], ch[q + ], ch[i]) > Cross(ch[i + ], ch[q], ch[i]))
q = (q +) % n;
ans = max(ans, max(SquareDis(ch[i], ch[q]), SquareDis(ch[i + ], ch[q + ])));
}
return ans;
} int main(){
POINT pnt[MAXN], res[MAXN];
int n;
while(EOF != scanf("%d",&n)){
for (int i = ; i < n; i++)
scanf("%d%d", &pnt[i].x, &pnt[i].y);
int count = Graham(pnt, res, n);
int ans = rotating_calipers(res, count);
printf("%d\n", ans);
}
return ;
}