补题：HOJ第二场Base Stations（UVALive-7825）（凸包）

「爱情、让人受尽委屈。」 2022-05-17 11:43 149阅读 0赞

题目链接：  
[UVALive-7825][]

题目大意：  
给你n个不同类型的点的坐标，求不同类型点之间最大距离为多少？

解题思路：  
由于点好多好多，所以之间暴力的话，肯定会TLE！！！  
所以我们需要先求出每种类型的凸包（用求凸包算法模板就好了），这样可以减少一些点之间距离的计算。  
此时如果我们直接拿两个凸包中的点两两去求距离，然后取最大，发现还是会TLE！！！

因此我们需要继续减少不必要的点与点之间的距离计算。  
当我们求完凸包A和凸包B之间的最大距离后，把凸包A和凸包B合并成一个新的凸包，然后新凸包继续和后面类型的凸包求最大距离，依次循环，不断更新最大距离

emmmm,曾经尝试过用旋转卡壳来求凸包之间的最大距离，但是老是WA，这题折腾了好多天，可以看一下我的血泪史！！！  
![这里写图片描述][70]  
最后终于AC了，不说了，都是泪，写到自闭

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    
    using namespace std;
    const int MAXN = 1e5+7;
    
    struct Points{
        int x,y;
        Points(){}
        Points(int x,int y):x(x),y(y){}
    
        Points operator +(const Points &p){
            return Points(x+p.x,y+p.y);
        }
        Points operator -(const Points &p){
            return Points(x-p.x,y-p.y) ;
        }
        Points operator *(const int &d){
            return Points(x*d,y*d);
        }
        bool operator <(const Points &p){
            return x==p.x?y<p.y:x<p.x;
        }
    };
    
    vector<Points> PP[105],ch[105];
    int flag[105];
    
    
    int Cross(Points A,Points B){
        return A.x*B.y-A.y*B.x;
    }
    
    //?? 
    int cross(Points A,Points B,Points C){
        return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
    }
    
    
    void ConvexHull (vector<Points> &p,int ty){
        sort(p.begin(),p.end());
        int m=0;
        for(int i=0; i<p.size(); ++i){
            while(m>1&&Cross(ch[ty][m-1]-ch[ty][m-2],p[i]-ch[ty][m-2])<=0) {
                ch[ty].pop_back();
                m=ch[ty].size();
            }
            ch[ty].push_back(p[i]);
            m=ch[ty].size();
        }
    
        int k=ch[ty].size();
        for(int i=p.size()-2;i>=0;--i){
    
            while(m>k&&Cross(ch[ty][m-1]-ch[ty][m-2],p[i]-ch[ty][m-2])<=0) {
                ch[ty].pop_back();
                m=ch[ty].size();
            }
            ch[ty].push_back(p[i]);
            m=ch[ty].size();
        }
    }
    
    int Getdist(Points A,Points B){
        return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
    }
    
    int Maxdist(vector<Points>& P,vector<Points>& Q){
        int ret=0;
        int len1=P.size();
        if(len1>1) len1--;
        int len2=Q.size();
        if(len2>1) len2--;
        for(int i=0; i<len1; ++i){
            for(int j=0; j<len2; ++j){
                ret=max(ret,Getdist(P[i],Q[j]));
            }
        }
        return ret;
    }
    
    void init(){
        memset(flag,0,sizeof(flag));
        for(int i=0; i<105; ++i){
            PP[i].clear();
            ch[i].clear();
        } 
    }
    
    int n;
    int main(){
        cin.sync_with_stdio(false);
        while(scanf("%d",&n)&&n){
            init();
            for(int i=1; i<=n; ++i){
                int x,y,t;
                scanf("%d%d%d",&x,&y,&t);
                flag[t]=1;
                Points p(x,y);
                PP[t].push_back(p);
            }
    
            for(int i=0; i<100; ++i){
                if(flag[i]){ 
                    ConvexHull(PP[i],i);
                //  for(int j=0; j<ch[i].size(); ++j) cout<<ch[i][j].x<<" "<<ch[i][j].y<<endl;
                }
            }
    
            int ans=0,t=0;
            for(int i=0; i<100; ++i){
                if(flag[i]){
                    t=i;
                    break;
                }
            }
            for(int j=0; j<100; ++j){
                if(t!=j&&flag[j]){
                    ans=max(ans,Maxdist(ch[t],ch[j]));
                    for(int i=0; i<PP[j].size(); ++i) PP[t].push_back(PP[j][i]);
                    ch[t].clear();
                    ConvexHull(PP[t],t);
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[UVALive-7825]: https://vjudge.net/problem/UVALive-7825
[70]: /images/20220517/2f0c9162cf3d4107be9a21c2e106a859.png