UESTC 1332 Beauty Contest(凸包直径)

你的名字 2021-05-02 12:19 414阅读 0赞

题意：给定n个点。求最远点对。

思路：模板题。

#include <iostream>
     #include <stdio.h>
     #include <cmath>
     #include <algorithm>
     #define max(x,y) ((x)>(y)?(x):(y))
     using namespace std;
     
     struct point
     {
         double x,y;
     
         point(){}
         point(double _x,double _y)
         {
             x=_x;
             y=_y;
         }
     
     
         void get()
         {
             scanf("%lf%lf",&x,&y);
         }
     };
     
     const double EPS=1e-8;
     const int MAX=100005;
     point p[MAX],q[MAX];
     int n,m;
     
     
     int DB(double x)
     {
         if(x>EPS) return 1;
         if(x<-EPS) return -1;
         return 0;
     }
     
     double Dis(point a,point b)
     {
         return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
     }
     
     //判断p在向量ab的哪一侧
     //右侧：返回正值
     //左侧：返回负值
     //在向量ab上返回0
     double cross(point a,point b,point p)
     {
         return (b.x-a.x)*(p.y-a.y)-(b.y-a.y)*(p.x-a.x);
     }
     
     int cmp(point a,point b)
     {
         double x=Dis(a,p[0]),y=Dis(b,p[0]);
         int flag=DB(cross(p[0],a,b));
         if(flag) return flag==1;
         return DB(x-y)<=0;
     }
     
     void Graham(point p[],int n,point q[],int &m)
     {
         point temp;
         int i,k=0,a,b;
         for(i=1;i<n;i++)
         {
             a=DB(p[i].y-p[k].y);
             b=DB(p[i].x-p[k].x);
             if(a==-1||!a&&b==-1) k=i;
         }
         if(k!=0) temp=p[0],p[0]=p[k],p[k]=temp;
         sort(p+1,p+n,cmp);
         q[0]=p[0];
         q[1]=p[1];
         p[n]=p[0];
         m=2;
         for(i=2;i<=n;i++)
         {
             while(m>1&&DB(cross(q[m-2],q[m-1],p[i]))<=0) m--;
             q[m++]=p[i];
         }
         m--;
     }
     
     
     double calMaxLen(point q[],int n)
     {
         q[n]=q[0];
         int i,p=1;
         double ans=0,x,y;
         for(i=0;i<n;i++)
         {
             while(1)
             {
                 x=cross(q[i],q[i+1],q[p+1]);
                 y=cross(q[i],q[i+1],q[p]);
                 if(DB(x-y)<=0) break;
                 p=(p+1)%n;
             }
             ans=max(ans,max(Dis(q[i],q[p]),Dis(q[i+1],q[p+1])));
         }
         return ans;
     }
     
     int main()
     {
         while(scanf("%d",&n)!=-1)
         {
             int i;
             for(i=0;i<n;i++) p[i].get();
             Graham(p,n,q,m);
             double ans=calMaxLen(q,m);
             printf("%.0lf\n",ans*ans);
         }
         return 0;
     }