nyoj253LK的旅行（旋转卡壳法） - c++编程基础

LK的旅行

时间限制：2000 ms | 内存限制：65535 KB 难度：5

描述

LK最近要去某几个地方旅行，她从地图上计划了几个点，并且用笔点了出来，准备在五一假期去这几个城市旅行。现在希望你找出她点的所有的点中距离最远的两个点的距离是多少。各个景点可以认为是在一个平面上。

输入

第一行有一个整数0 输出

每组数据输出距离最远的点对的距离的平方.

样例输入

样例输出

做这个题之前最好先做下78圈水池这题，这两个题差不多，区别在于一个是求哪些点在凸包内，这个是求凸包的两个最远的点的距离的平方。

#include
      
       
#include
       
         #include
        
          #define NN 100005 #define max(a,b) ((a)>(b)?(a):(b)) const int INF=1<<30; typedef struct Point{ int x,y; }P; P a[NN],q[NN]; int top; int dis_2(P p1,P p2) { return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y); } int xx(P p,P p1,P p2) { return (p1.x-p.x)*(p2.y-p.y)-(p1.y-p.y)*(p2.x-p.x); } int comp(const void *x,const void *y) { P i=*(P *)x; P j=*(P *)y; if(i.x!=j.x) return i.x-j.x; else return i.y-j.y; } int main() { int N,i,n; scanf("%d",&N); while(N--) { scanf("%d",&n); for(i=0;i
         
          =1 && xx(q[top-1],q[top],a[i])>=0) top--; q[++top]=a[i]; } int t=top; for(i=n-1;i>=0;i--)//上凸包 { if(a[i].x==q[top].x && a[i].y==q[top].y) continue; while(top>t && xx(q[top-1],q[top],a[i])>=0) top--; q[++top]=a[i]; } double ans=0.0; t=1; for(i=0;i
          
            xx(q[i+1],q[t+1],q[i])) t=(t+1)%top; ans=max(ans,max(dis_2(q[i],q[t]),dis_2(q[i+1],q[t+1]))); } printf("%.0lf\n",ans); } return 0; }