题意:给出一个多边形,求出多边形最远两点距离的平方。


题解:旋转卡壳模板题,先求凸包再用Andrew求最远点对即可。


代码:

StatusAccepted
Time219ms
Memory3128kB
Length2774
LangG++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const double eps=1e-12;
const double pi=acos(-1.0);
int dcmp(double x){ if(fabs(x)<eps)return 0;else return x<0?-1:1;}
struct Point{
    int id;
    double x, y;
    Point(){}
    Point(double _x, double _y){x=_x,y=_y;}
    void input(){scanf("%lf%lf", &x, &y);}
    void output(){printf("%.2lf %.2lf\n", x, y);}
    bool operator==(const Point &p)const{return dcmp(x-p.x)==0 && dcmp(y-p.y)==0;}
    bool operator <(const Point &p)const{return dcmp(x-p.x)==0?dcmp(y-p.y)<0:x<p.x;}
    double operator ^(const Point &p)const{return x*p.y-y*p.x;} //叉积
    double operator *(const Point &p)const{return x*p.x+y*p.y;} //点积
    Point operator +(const Point &p)const{return Point(x+p.x, y+p.y);}
    Point operator -(const Point &p)const{return Point(x-p.x, y-p.y);}
    Point operator *(const double &k)const{return Point(x*k, y*k);}
    Point operator /(const double &k)const{return Point(x/k, y/k);}
    double len(){return sqrt(x*x+y*y);}                         //长度
    double len2(){return x*x+y*y;}                              //长度的平方
    double distance(Point p){return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));} //距离
};
vector<Point> getConvexHull(vector<Point> res){
    vector<Point> ans;
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    int cnt=0;
    for(int i=0;i<res.size();i++){
        while(cnt>1 && dcmp((ans[cnt-1]-ans[cnt-2])^(res[i]-ans[cnt-2]))<=0)ans.pop_back(),cnt--;
        ans.push_back(res[i]),cnt++;
    }
    int s=cnt;
    for(int i=int(res.size())-2;i>=0;--i){
        while(cnt>s && dcmp((ans[cnt-1]-ans[cnt-2])^(res[i]-ans[cnt-2]))<=0)ans.pop_back(),cnt--;
        ans.push_back(res[i]),cnt++;
    }
    if(cnt>1)ans.pop_back();
    return ans;
}
pair<int, int> getConvexDiameter(vector<Point> res){
    pair<int, int> ans;
    double maxd=0;
    int j=1, num=res.size();
    res.push_back(res[0]);
    for(int i=0;i<num;i++){
        while(dcmp( ((res[i+1]-res[i])^(res[j+1]-res[i])) - ((res[i+1]-res[i])^(res[j]-res[i])) )>0)j=(j+1)%num;
        double d=res[i].distance(res[j]);
        if(d>maxd)ans.first=i, ans.second=j,maxd=d;
    }
    return ans;
}
int N, L;
int main(){
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    while(~scanf("%d", &N)){
        vector<Point> res;
        Point p;
        for(int i=0;i<N;i++){
            scanf("%lf%lf", &p.x, &p.y);
            p.id=i+1;
            res.push_back(p);
        }
        vector<Point> hull=getConvexHull(res);
        pair<int, int> ans=getConvexDiameter(hull);
        int val=(hull[ans.first]-hull[ans.second]).len2();
        printf("%d\n", val);
    }
    return 0;
}