Rotating Calipers (TFOSS)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

#define x first
#define y second

vector<pll> v;
vector<pll> h;

ll cross(pll o, pll a, pll b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

ll sqr(ll x) { return x*x; }

// máximo da distância ao quadrado de a<->opo ou b<->opo
ll dist(pll a, pll b, pll opo) {
    return max(sqr(a.x - opo.x) + sqr(a.y - opo.y),
            sqr(b.x - opo.x) + sqr(b.y - opo.y));
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--) {
        v.clear();
        int n;
        scanf("%d", &n);

        ll a,b;
        for (int i = 0; i < n; i++)
            scanf("%lld %lld", &a, &b), v.push_back({a,b});

        if (n == 1) { printf("%d\n", 0); continue;}

        // ordena os pontos pelo x e depois pelo y
        sort(v.begin(), v.end());
        h.clear();

        // acha o convex hull (upper hull + lower hull) (inclue pontos colineares)
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            while (cnt > 1 && cross(h[cnt-2], h[cnt-1], v[i]) >= 0) h.pop_back(), cnt--;
            h.push_back(v[i]); cnt++;
        }

        int cnt0 = cnt;

        for (int i = n-2; i >= 0; i--) {
            while (cnt - cnt0 > 0 && cross(h[cnt-2], h[cnt-1], v[i]) >= 0) h.pop_back(), cnt--;
            h.push_back(v[i]); cnt++;
        }

        // faz rotating calipers e atualiza resposta
        ll ans = 0;
        int opo = 1;
        // itera pelos pontos:
        for (int i = 1; i < h.size(); i++) {
            // atualiza a reta oposta (par de pontos que definem a reta);
            while (1) {
                int next = opo+1 < h.size() ? opo+1 : 1;
                if (dist(h[i-1], h[i], h[opo]) <= dist(h[i-1], h[i], h[next]))
                    opo = next;
                else
                    break;
            }

            ans = max(ans, dist(h[i], h[i-1], h[opo]));
        }

        printf("%lld\n", ans);
    }
}