Graham求凸包，再旋转卡壳
第一次自己写Graham，出了挺多错误，刚开始还以为有什么陷阱
说下要注意事项
top–前面是<=0
还有就是求完凸包之后再用旋转卡壳的时候注意要用stack数组进行旋转卡壳，还有stack[top]=stack[0]
#include <iostream>#include <cstdlib>#include <cstdio>#include <cmath>#include<algorithm>#define N 50005using namespace std;const double eps=1e-5;struct Point {int x,y;Point (){}Point (int xx,int yy) {x=xx;y=yy;}Point operator -(const Point b)const {return Point(x-b.x,y-b.y);}int operator ^(const Point b)const {return x*b.y-y*b.x;}};int n,top;Point p[N],stack[N];int dist(Point a,Point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}int cmp(Point a,Point b) {//逆时针int tmp=(a-p[0])^(b-p[0]);if(tmp == 0 ) return dist(a,p[0]) – dist(b,p[0]) <= 0;else return tmp>0;}void Graham(){int k=0;for(int i=0;i<n;i++){if(p[i].y<p[k].y || (p[i].y==p[k].y && p[i].x<p[k].x)) k=i;}swap(p[0],p[k]);sort(p+1,p+n,cmp);if(n<=2){for(int i=0;i<n;i++) stack[i]=p[i];top=n;return;}stack[0]=p[0]; stack[1]=p[1];top=2;for(int i=2;i<n;i++){while(top>=2 && ((stack[top-1]-stack[top-2])^(p[i]-stack[top-2]))<=0) top–;stack[top++]=p[i];}}int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif // ONLINE_JUDGEwhile(scanf("%d",&n)!=EOF){for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);Graham();for(int i=0;i<top;i++) {p[i]=stack[i];//printf("%d %d\n",p[i].x,p[i].y);}p[top]=p[0];int ans=0;Point a,b;for(int i=0,j=1;i<top;i++){while(((p[i+1]-p[i])^(p[j]-p[i]))<((p[i+1]-p[i])^(p[j+1]-p[i]))) j=(j+1)%top;if(dist(p[i],p[j])>=ans) ans=dist(p[i],p[j]);if(dist(p[i+1],p[j+1])>=ans) ans=dist(p[i+1],p[j+1]);//处理两条边平行的特殊情况}printf("%d\n",ans);}return 0;}
，青春一经典当即永不再赎
