旋转卡壳

Luogu P1452 USACO03FALL Beauty Contest G /【模板】旋转卡壳

注意 stk 数组要开二倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// ...
void EvaConv(Point p[], int n) {/* ... */}
double Rotate(Point p[], int n) {
    EvaConv(p, n);
    if (top <= 2) {
        return dist(p[stk[1]], p[stk[top]]);
    }
    double ans = 0;
    copy(stk + 1, stk + top + 1, stk + top + 1);
    for (int i = 1, j = 3; i <= top; ++i) {
        while (j < top * 2 && area(p[stk[i]], p[stk[i + 1]], p[stk[j]]) <= area(p[stk[i]], p[stk[i + 1]], p[stk[j + 1]])) ++j;
        ans = max(ans, max(dist(p[stk[i]], p[stk[j]]), dist(p[stk[i + 1]], p[stk[j]])));
    }
    return ans;
}

最小矩形覆盖

Luogu P3187 HNOI2007 最小矩形覆盖

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
// ...
void EvaConv(Point p[], int n) {/* ... */}
void Rotate(Point p[], int n) {
    EvaConv(p, n);
    if (top <= 2) {
        puts("Error!");
        exit(1);
    }
    copy(stk + 1, stk + top + 1, stk + top + 1);
    for (int i = 1, j = 3, k = 2, l, topidx = top * 2; i <= top; ++i) {
        while (j < topidx && area(p[stk[i]], p[stk[i + 1]], p[stk[j]]) <= area(p[stk[i]], p[stk[i + 1]], p[stk[j + 1]])) ++j;
        while (k < topidx && proj(p[stk[i]], p[stk[i + 1]], p[stk[k]]) <= proj(p[stk[i]], p[stk[i + 1]], p[stk[k + 1]])) ++k;
        if (i == 1) l = j;
        while (l < topidx && proj(p[stk[i]], p[stk[i + 1]], p[stk[l]]) >= proj(p[stk[i]], p[stk[i + 1]], p[stk[l + 1]])) ++l;
        double h = poi_dist_str(p[stk[i]], p[stk[i + 1]], p[stk[j]]);
        Point kproji = poi_proj_str(p[stk[i]], p[stk[i + 1]], p[stk[k]]), lproji = poi_proj_str(p[stk[i]], p[stk[i + 1]], p[stk[l]]);
        double w = length(kproji - lproji);
        if (ans > h * w) {
            Point jprojk = poi_proj_str(kproji + rotate(lproji - kproji, -PI / 2), kproji, p[stk[j]]),
                  jprojl = poi_proj_str(lproji + rotate(kproji - lproji, PI / 2), lproji, p[stk[j]]);
            ans = h * w;
            ansp[0] = lproji; ansp[1] = kproji; ansp[2] = jprojk; ansp[3] = jprojl;
        }
    }
}