题解 | #小红选点#

B题其实可以做到O(n log n)的时间复杂度。
我们可以对点集求一个凸包，然后对应问题就转变为求凸包的直径。可以使用旋转卡壳O(n)求解。
算法瓶颈在求凸包的排序，是O(n log n)的时间复杂度。
下面贴一下板子

using ld = long double;
const ld PI = acos(-1);
const ld EPS = 1e-7;
const ld INF = numeric_limits<ld>::max();
#define cc(x) cout << fixed << setprecision(x);

ld fgcd(ld x, ld y) { // 实数域gcd
    return abs(y) < EPS ? abs(x) : fgcd(y, fmod(x, y));
}
template<class T, class S> bool equal(T x, S y) {
    return -EPS < x - y && x - y < EPS;
}
template<class T> ll sign(T x) {
    if (-EPS < x && x < EPS) return 0;
    return x < 0 ? -1 : 1;
}
template<class T> T sqr(T x) {
    return x * x;
}

template<class T> struct Point { // 在C++17下使用 emplace_back 绑定可能会导致CE！
    T x, y;
    Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {} // 初始化
    template<class U> operator Point<U>() { // 自动类型匹配
        return Point<U>(U(x), U(y));
    }
    Point &operator+=(Point p) & { return x += p.x, y += p.y, *this; }
    Point &operator+=(T t) & { return x += t, y += t, *this; }
    Point &operator-=(Point p) & { return x -= p.x, y -= p.y, *this; }
    Point &operator-=(T t) & { return x -= t, y -= t, *this; }
    Point &operator*=(T t) & { return x *= t, y *= t, *this; }
    Point &operator/=(T t) & { return x /= t, y /= t, *this; }
    Point operator-() const { return Point(-x, -y); }
    friend Point operator+(Point a, Point b) { return a += b; }
    friend Point operator+(Point a, T b) { return a += b; }
    friend Point operator-(Point a, Point b) { return a -= b; }
    friend Point operator-(Point a, T b) { return a -= b; }
    friend Point operator*(Point a, T b) { return a *= b; }
    friend Point operator*(T a, Point b) { return b *= a; }
    friend Point operator/(Point a, T b) { return a /= b; }
    friend bool operator<(Point a, Point b) {
        return equal(a.x, b.x) ? a.y < b.y - EPS : a.x < b.x - EPS;
    }
    friend bool operator>(Point a, Point b) { return b < a; }
    friend bool operator==(Point a, Point b) { return !(a < b) && !(b < a); }
    friend bool operator!=(Point a, Point b) { return a < b || b < a; }
    friend auto &operator>>(istream &is, Point &p) {
        return is >> p.x >> p.y;
    }
    friend auto &operator<<(ostream &os, Point p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};
template<class T> struct Line {
    Point<T> a, b;
    Line(Point<T> a_ = Point<T>(), Point<T> b_ = Point<T>()) : a(a_), b(b_) {}
    template<class U> operator Line<U>() { // 自动类型匹配
        return Line<U>(Point<U>(a), Point<U>(b));
    }
    friend auto &operator<<(ostream &os, Line l) {
        return os << "<" << l.a << ", " << l.b << ">";
    }
};


template<class T> T disEx(Pt a1,Pt a2)
{
    return (a1.x-a2.x)*(a1.x-a2.x)+(a1.y-a2.y)*(a1.y-a2.y);
}

template<class T> T cross(Point<T> a, Point<T> b) { // 叉乘
    return a.x * b.y - a.y * b.x;
}
template<class T> T cross(Point<T> p1, Point<T> p2, Point<T> p0) { // 叉乘 (p1 - p0) x (p2 - p0);
    return cross(p1 - p0, p2 - p0);
}

template<class T> T dot(Point<T> a, Point<T> b) { // 点乘
    return a.x * b.x + a.y * b.y;
}
template<class T> T dot(Point<T> p1, Point<T> p2, Point<T> p0) { // 点乘 (p1 - p0) * (p2 - p0);
    return dot(p1 - p0, p2 - p0);
}

template <class T> ld dis(T x1, T y1, T x2, T y2) {
    ld val = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    return sqrt(val);
}
template <class T> ld dis(Point<T> a, Point<T> b) {
    return dis(a.x, a.y, b.x, b.y);
}

template<class T> vector<Point<T>> staticConvexHull(vector<Point<T>> &A, ll flag = 1) {
    ll n = A.size();
    if (n <= 2) { // 特判
        return A;
    }
    vector<Point<T>> ans(n * 2);
    sort(A.begin(), A.end());
    ll now = -1;
    for (ll i = 0; i < n; i++) { // 维护下凸包
        while (now > 0 && cross(A[i], ans[now], ans[now - 1]) <= 0) {
            now--;
        }
        ans[++now] = A[i];
    }
    ll pre = now;
    for (ll i = n - 2; i >= 0; i--) { // 维护上凸包
        while (now > pre && cross(A[i], ans[now], ans[now - 1]) <= 0) {
            now--;
        }
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}

template<class T>pair<Pt,Pt> GetConvexHullDis(vector<Pt> A)//返回平方，并特判为一条线的情况
{

    ll cnt=0;
    for(auto ne:A) 
    {
        if(cross(A[0],A[1],ne)!=0) break;
        ++cnt;
    }
    if(cnt==A.size()) 
    {
        Pt a1=A[0],a2=A[0];
        for(auto ne:A) a1=max(a1,ne),a2=min(a2,ne);
        return {a1,a2};
    }

    ll w=0; 
    T jj1=disEx(A[w],A[0]); T jj2=disEx(A[w],A[1]);
    T ans=max(jj1,jj2);
    pair<Pt,Pt> res;
    if(jj1>jj2) res={A[w],A[0]};
    else res={A[w],A[1]};

    for(ll i=0;i<A.size();i++)
    {
        ll j=(i+1)%A.size();
        ll ne=(w+1)%A.size();
        while((-cross(A[ne],A[i],A[j]))>=(-cross(A[w],A[i],A[j]))) w=ne,ne=(w+1)%A.size();
        jj1=disEx(A[w],A[i]); jj2=disEx(A[w],A[j]);
        pair<Pt,Pt> tem;
        if(jj1>jj2) tem={A[w],A[i]};
        else tem={A[w],A[j]};
        jj1=max(jj1,jj2);
        if(ans<jj1) ans=jj1,res=tem;
    }
    return res;
}