凸包+旋转卡壳--POJ 2187
题意：求平面点集上的最远点对
思路：先求出凸包，最远的对肯定在凸包上面，但是下面暴力的话时间复杂度o(n^2)，旋转卡壳也是遍历，不过遍历的时候把复杂度降下来啦！
旋转卡壳见：http://blog.csdn.net/hitfanyu/article/details/5522589
#include <iostream>#include<algorithm>#include<cmath>#include<cstdio>#include<cstdlib>#define eps 1e-8using namespace std;struct point{ int x,y;} p[50005],res[50005];int cross(point p0, point p1, point p2){ return(p1.x- p0.x) * (p2.y- p0.y) - (p1.y- p0.y) * (p2.x- p0.x);}int dist(point a,point b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}bool cmp(point a, point b){ return(a.y< b.y|| (a.y== b.y&& a.x< b.x));}int Graham(int n){ int len, top=1; sort(p, p+ n, cmp); res[0] = p[0]; res[1] = p[1]; for(int i=2; i< n; i++) { while(top&& cross(res[top], res[top-1], p[i])<=eps)top--; res[++ top] = p[i]; } len= top; res[++ top] = p[n-2]; for(int i= n-3; i>=0; i--) { while(top!= len&& cross(res[top], res[top-1], p[i])<=eps)top--; res[++ top] = p[i]; } return top;}int diameter(int n){ int i,j=1,ans=-1; res[n]=res[0]; for(i=0; i<n; i++) { while(fabs(cross(res[i+1],res[j+1],res[i]))>fabs(cross(res[i+1],res[j],res[i]) )) j=(j+1)%n; ans=max(ans,max(dist(res[i],res[j]),dist(res[i+1],res[j+1]))); } return ans;}int main(){ int n; while(scanf("%d",&n)!=EOF) { for(int i=0; i<n; i++) cin >> p[i].x >> p[i].y; int top=Graham(n); cout << diameter(top) << endl; } return 0;}