Rotating Calipers

From EOJ Wiki
Jump to navigation Jump to search
ld rotatingCalipers(VPT& qs) {
    int n = qs.size();
    if (n == 2)
        return dist2(qs[0], qs[1]);
    int i = 0, j = 0;
    for (int k = 0; k < n; ++k) {
        if (!(qs[i] < qs[k])) i = k;
        if (qs[j] < qs[k]) j = k;
    }
    ld res = 0;
    int si = i, sj = j;
    while (i != sj || j != si) {
        res = max(res, dist2(qs[i], qs[j]));
        if (dcmp(cross(qs[(i+1)%n] - qs[i], qs[(j+1)%n] - qs[j])) < 0)
            i = (i + 1) % n;
        else j = (j + 1) % n;
    } 
    return res;
}

int main() {
    int n;
    while (cin >> n) {
        VPT v(n);
        for (int i = 0; i < n; ++i)
            cin >> v[i];
        convex_hull(v);
        printf("%.0f\n", rotatingCalipers(v));
    }
}