Как для выпуклого многоугольника быстро найти диаметр (самую далёкую пару вершин) методом вращающихся калиперов?

Идея вращающихся калиперов (rotating calipers): самая далёкая от данной вершины точка — это «антиподальная» вершина. При обходе оболочки по периметру антиподальная вершина монотонно двигается в том же направлении, поэтому её можно вести вторым указателем, не сбрасывая — отсюда суммарно O(n).

// hull — выпуклая оболочка, CCW, без повторов
long long convexDiameter(const vector<P>& h) {
    int n = h.size();
    if (n == 1) return 0;
    if (n == 2) return (h[0]-h[1]).len2();
    long long best = 0;
    int j = 1;
    for (int i = 0; i < n; i++) {
        int ni = (i + 1) % n;
        // двигаем j, пока площадь треугольника растёт (j удаляется)
        while (abs((h[ni]-h[i]).cross(h[(j+1)%n]-h[i])) >
               abs((h[ni]-h[i]).cross(h[j]-h[i]))) j = (j + 1) % n;
        best = max(best, max((h[i]-h[j]).len2(), (h[ni]-h[j]).len2()));
    }
    return best; // квадрат диаметра
}

Для каждого ребра i→ni находим самую удалённую от него вершину j (по |cross| — это высота). Поскольку j только продвигается вперёд по кругу, общий путь обоих указателей O(n). Возвращаю квадрат расстояния, в целых числах — без sqrt, точно. Предполагается, что вход уже выпуклая оболочка (её строим за O(n log n)).