跳转至

旋转卡壳

习题

P1452 [USACO03FALL] Beauty Contest G /【模板】旋转卡壳 - 洛谷

求凸包的直径.

求凸包后, 枚举边, 找到最远的点, 计算点到直线的距离.

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
{ 计算几何基础 }
{ 二维凸包 }
Tdouble RoatingCalipers(const vector<Point> &p) {
    if (p.size() == 3) return (p[0] - p[1]).length();
    int cur = 0, len = p.size();
    Tdouble ans = 0;
    for (int i = 0 ; i < len - 1 ; i++) {
        Line line(p[i], p[i + 1]);
        while (sgn(distanceLine(p[cur], line) - distanceLine(p[(cur + 1) % len], line)) <= 0) {
            cur = (cur + 1) % len;
        }
        ans = max({ans, (p[i] - p[cur]).length(), (p[i + 1] - p[cur]).length()});
    } 
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<Point> a(n);
    for (int i = 0 ; i < n ; i++) {
        cin >> a[i];
    }
    auto c = ConvexHull2D(a);
    auto d = RoatingCalipers(c);
    cout << int(d * d);
    return 0;
}

P3187 [HNOI2007] 最小矩形覆盖 - 洛谷

求覆盖 \(n\) 个点且面积最小的矩形, 以及该矩形的四个顶点

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
{ 计算几何基础 }
{ 二维凸包 }
#define func(a) (sgn(a) < 0 ? a = -a : 0.0)
pair<array<Point, 4>, Tdouble> RoatingCalipers(const vector<Point> &p) {
    Tdouble res, ans = 1e100;
    int a = 1, b = 1, c = 1, len = p.size();
    array<Point, 4> point;
    for (int i = 1 ; i < len ; i++) {
        Vector v1 = p[i - 1] - p[i], v2 = p[i] - p[i - 1];
        while (sgn(cross(p[(a + 1) % len] - p[i], v1) - cross(p[a] - p[i], v1) >= 0)) {
            a = (a + 1) % len;
        }
        while (sgn(dot(p[(b + 1) % len] - p[i], v1) - dot(p[b] - p[i], v1)) <= 0) {
            b = (b + 1) % len;
        }
        if (i == 1) c = a;
        while (sgn(dot(p[(c + 1) % len] - p[i - 1], p[i] - p[i - 1]) - dot(p[c] - p[i - 1], p[i] - p[i - 1])) <= 0) {
            c = (c + 1) % len;
        }
        Tdouble dis = v2.length();
        Tdouble L = dot(p[c] - p[i], v1) / dis;
        Tdouble R = dot(p[b] - p[i - 1], v2) / dis;
        Tdouble H = fabs(area2(p[i], p[i - 1], p[a])) / dis;
        func(L);func(R);func(H);
        res = (L + R - dis) * H;
        if (res < ans) {
            ans = res;
            point[0] = p[i] - v2 * (L / dis);
            point[1] = point[0] + v2 * ((L + R - dis) / dis);
            point[2] = point[1] + (p[b] - point[1]) * (H / (p[b] - point[1]).length());
            point[3] = point[2] + v1 * ((L + R - dis) / dis);
        }
    }
    return {point, ans};
}
#undef func(a)
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<Point> a(n);
    for (int i = 0 ; i < n ; i++) {
        cin >> a[i];
    }
    auto c = ConvexHull2D(a);
    auto [point, ans] = RoatingCalipers(c);
    cout << fixed << setprecision(5) << ans << "\n";
    int pos = 0;
    for (int i = 0 ; i < 4 ; i++) {
        if (point[i].y < point[pos].y || (point[i].y == point[pos].y && point[i].x < point[pos].x)) {
            pos = i;
        }
    }
    for (int i = 0 ; i < 4 ; i++) {
        int k = (pos + i) % 4;
        if (sgn(point[k].x) == 0) point[k].x = 0.0;
        if (sgn(point[k].y) == 0) point[k].y = 0.0;
        cout << point[k] << "\n";
    }
    return 0;
}