今天写一道题的时候用了旋转卡壳

交。。交。。交

WA。。WA。。WA

不知道发生了什么，于是把旋转卡壳换成了$O(N^2)$的暴力

就AC了QAQ

于是蒟蒻就精分了

所以，请问这个旋转卡壳有科学性错误吗？

const double eps = 1e-8;
const double inf = 1000000000;

struct Poi {
    double x, y;
    Poi(double X = 0, double Y = 0):x(X), y(Y) { }
}p[N], ch[N];
typedef Poi Vec;

Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y); }

int dcmp(double x) { // 精度check
    if (abs(x) < eps) return 0;
    else return x > 0 ? 1 : -1;
}

double dist(Poi a, Poi b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); } //距离

double cross(Vec a, Vec b) { return a.x * b.y - a.y * b.x; } //叉积

void RC(int n, Poi* p) {
    sort(p, p + n);
    double mx = -inf; Poi p1, p2;
    p[n] = p[0];
    for(int u = 0, v = 1; u < n; u++) {
        for(;;) {
            double tmp = cross(p[u + 1] - p[u], p[v + 1] - p[v]);
            if (dcmp(tmp) <= 0) {
                double dis = dist(p[u], p[v]);
                if (dis > mx) mx = dis, p1 = p[u], p2 = p[v];
                dis = dist(p[u], p[v + 1]);
                if (dis > mx) mx = dis, p1 = p[u], p2 = p[v + 1]; 
                break;
            }
            v = (v + 1) % n;
        }
    }
    printf("%.4lf %.4lf %.4lf %.4lf\n", p1.x, p1.y, p2.x, p2.y);
}

谢谢诸位QAQ