C++(g++ 7.5.0) 解法, 执行用时: 99ms, 内存消耗: 2604K, 提交时间: 2022-10-27 18:06:42

/*
 * @Author: JorD
 * @LastEditTime: 2022-10-27 18:06:21
 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Point{
    ll x, y;
};
vector<Point> p;
double operator ^ (Point a, Point b){
    return a.x * b.y - a.y * b.x;
}
Point operator - (Point a, Point b){
    return {a.x - b.x, a.y - b.y}; 
}
vector<Point> a, b;
bool check(Point x, Point y, Point z){
    return ((y - x) ^ (z - y)) <= 0.0;
}
ll dist(Point a, Point b){
    return ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void Convex(){
    sort(p.begin(), p.end(), [&](Point a, Point b){
        if(a.x == b.x) return a.y < b.y;
        return a.x < b.x;
    });
    int idx = 0;
    for(auto x:p){
        while(a.size() > 1&&check(*prev(a.end() - 1), a.back(), x)) a.pop_back();
        a.push_back(x);
    }
    p.pop_back(); reverse(p.begin(), p.end());
    idx = a.size();
    for(auto x:p){
        while(a.size() > idx&&check(*prev(a.end() - 1), a.back(), x)) a.pop_back();
        a.push_back(x);
    }
}
int main(){
    int n;
    cin >> n;
    while(n --){
        ll x, y;
        cin >> x >> y;
        p.push_back({x, y});
    }
    Convex();
    ll res = 0;
    int m = a.size();
    a.push_back(a[0]);
    for(int i = 0, j = 1;i < m;i ++){
        res = max(res, max(dist(a[i], a[j]), dist(a[i + 1], a[j])));
        while(((a[j] - a[i + 1]) ^ (a[i] - a[i + 1])) < ((a[j + 1] - a[i + 1]) ^ (a[i] - a[i + 1]))){
            j = (j + 1) % m;
            res = max(res, max(dist(a[i], a[j]), dist(a[i + 1], a[j])));
        }
    }
    cout << res << endl;
}

C++(clang++ 11.0.1) 解法, 执行用时: 64ms, 内存消耗: 1996K, 提交时间: 2022-12-17 12:19:45

#include<algorithm>
#include<stdio.h>
#include<math.h>
#define ll long long
using namespace std;
struct v{ll x,y;}p[100002],d[100002];
bool f(v a,v b,v c,v d){return atan2(a.y-c.y,a.x-c.x)<=atan2(b.y-d.y,b.x-d.x);}
bool cm(v a,v b){return a.y-b.y?a.y>b.y:a.x<b.x;}
ll g(ll x){return x*x;}
ll N,j,k,i;
int main(){
	for(scanf("%lld",&N);i<N;++i)scanf("%lld%lld",&p[i].x,&p[i].y);
	for(sort(p,p+N,cm);j<N;d[k].x=p[j].x,d[k].y=p[j].y,++k,++j)while(k>1&&f(p[j],d[k-1],d[k-1],d[k-2]))--k;
	for(i-=2;i;d[k].x=p[i].x,d[k].y=p[i].y,++k,--i)while(k>1&&f(p[i],d[k-1],d[k-1],d[k-2]))--k;
	for(N=i;i<k;++i)for(j=i+1;j<k;++j)N=max(N,g(d[i].x-d[j].x)+g(d[i].y-d[j].y));
	printf("%lld",N);
}