Dyd's Blog

He who has a strong enough why can bear almost any how.

旋转卡壳

Posted on Edited on In
Symbols count in article: 4.9k Reading time ≈ 4 mins.

四个多音字，怎么读啊~

旋转卡壳

因为要讲就重新搞一下（其实我也不是很会这玩意）

问题引入

平面上有 $n$ 个点，求平面最远点对（即凸包直径）

由该问题也可以得到一个性质：平面最远的点对一定是凸包上的两点

简证（口胡）：设最远点对有一点 $A$ 不在凸包上，另一点 $B$ 任意，设射线 $BA$ 交凸包于 $C$ ，设 $C$ 在凸包的边 $DE$ 上，有 $AB < CB < DB$

过程

有了如上性质，我们就只需要考虑凸包上的点

先取两条平行于 $x$ 轴的直线，让它们“卡”住这个凸包，然后逆时针旋转，时刻保证两线平行，整个过程中两直线距离的最大值就是凸包直径

卡

正确性显然（然鹅图里那个图形好像不是凸包）

但角度是无穷的，我们不可能真的让两条线旋转一周

考虑用点的距离替代两线之间的距离，我们称把两线“卡”住的两个点称为对踵点（即图中绿色的点），明显，对踵点成对出现，且距离最大的一对对踵点之间的距离就是凸包直径（一个显然但巧妙的性质是，对踵点最多有 $\frac{3n}{2}$ 对）

思考对踵点的改变条件

对踵点

如图，当黑线旋转至红线位置时，绿色对踵点变成橙色

而红线位置就是凸包的边！换句话说，只要对凸包每条边，求出离这条边最远的点即可

那么如何求呢？我们逆时针扫描每条边，明显要求的最远点也将逆时针旋转，可以用一个双指针，面积法判定两个点到一条边的距离，时间是 $O(n)$ 的，加上求凸包的时间，共是 $O(n \log n)$ 的

ps：其实可以把旋转卡壳理解为当你枚举边的时候，距离边最远的点是单调的

代码

板子

由于是整数运算，精度足够

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
#include <bits/stdc++.h>
#define fi first
#define se second
using DB = double;
using PDD = std::pair<double, double>;
const int N = 5e4 + 100;
int stk[N], top;
bool vis[N];
PDD operator - (PDD x, PDD y){ return {x.fi - y.fi, x.se - y.se}; }
DB operator * (PDD x, PDD y){ return x.fi * y.se - x.se * y.fi; }
DB operator & (PDD x, PDD y){ return x.fi * y.fi + x.se * y.se; }
DB area(PDD x, PDD y, PDD z){ return (y - x) * (z - x); }
DB dist2(PDD x, PDD y){ return (y - x) & (y - x); }
void convex(PDD *x, int n)
{
	std::sort(x, x + n);
	for (int i = 0; i < n; ++i)
	{
		while (top >= 2)
		{
			DB t = area(x[stk[top - 2]], x[stk[top - 1]], x[i]);
			if (t < 0) vis[stk[--top]] = false;
			else if (!t) --top;
			else break;
		}
		vis[stk[top++] = i] = true;
	}
	vis[0] = false;
	for (int i = n - 1; ~i; --i) if (!vis[i])
	{
		while (top >= 2 && area(x[stk[top - 2]], x[stk[top - 1]], x[i]) < 0) --top;
		stk[top++] = i;
	}
	--top;
}
DB rotcal(PDD *x, int n)
{
	if (top <= 2) return dist2(x[0], x[n - 1]);
	DB res = 0;
	for (int i = 0, j = 2; i < top; ++i)
	{
		PDD a = x[stk[i]], b = x[stk[i + 1]];
		while (area(a, b, x[stk[j]]) < area(a, b, x[stk[j + 1]])) j = j + 1 >= top ? 0 : j + 1;
		res = std::max(res, std::max(dist2(a, x[stk[j]]), dist2(b, x[stk[j]])));
	}
	return res;
}
int main()
{
	int n;
	PDD p[N];
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%lf %lf", &p[i].fi, &p[i].se);
	convex(p, n);
	printf("%.0lf\n", rotcal(p, n));
	return 0;
}

例题一

最小矩阵覆盖

思路：

Lemma ：最小面积矩形一定有一条边和凸包重合

证明略

枚举一条边，另外三条线旋转卡即可

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
#define fi first
#define se second
using DB = double;
using PDD = std::pair<double, double>;
const int N = 50000 + 100;
const DB eps = 1e-12;
int stk[N], top;
bool vis[N];
DB ans = 1e18;
std::array<PDD, 4> as;
int cmp(DB x, DB y)
{
    if (fabs(x - y) < eps) return 0;
    return x > y ? 1 : -1;
}
PDD operator - (PDD x, PDD y){ return {x.fi - y.fi, x.se - y.se}; }
PDD operator + (PDD x, PDD y){ return {x.fi + y.fi, x.se + y.se}; }
PDD operator / (PDD x, DB y){ return {x.fi / y, x.se / y}; }PDD operator * (PDD x, DB y){ return {x.fi * y, x.se * y}; }
DB operator * (PDD x, PDD y){ return x.fi * y.se - x.se * y.fi; }
DB operator & (PDD x, PDD y){ return x.fi * y.fi + x.se * y.se; }
DB area(PDD x, PDD y, PDD z){ return (y - x) * (z - x); }
DB mo(PDD x){ return std::sqrt(x & x); }
DB proj(PDD x, PDD y, PDD z)
{
    y = y - x, z = z - x;
    return y & z / mo(y);
}
PDD rot(PDD x, DB th){ return {x.fi * std::cos(th) + x.se * std::sin(th), -x.fi * std::sin(th) + x.se * std::cos(th)}; }
PDD norm(PDD x){ return x / mo(x); }
void convex(PDD *x, int n)
{
    top = 0;
    std::sort(x, x + n);
    for (int i = 0; i < n; ++i)
    {
        while (top >= 2)
        {
            int t = cmp(area(x[stk[top - 2]], x[stk[top - 1]], x[i]), 0);
            if (t < 0) vis[stk[--top]] = false;
            else if (!t) --top;
            else break;
        }
        vis[stk[top++] = i] = true;
    }
    vis[0] = false;
    for (int i = n - 1; ~i; --i) if (!vis[i])
    {
        while (top >= 2 && cmp(area(x[stk[top - 2]], x[stk[top - 1]], x[i]), 0) < 0) --top;
        stk[top++] = i;
    }
    --top;
}
void rotcal(PDD *x, int n)
{
    for (int i = 0, a = 2, b = 1, c; i < top; ++i)
    {
        PDD d = x[stk[i]], e = x[stk[i + 1]];
        while (cmp(area(d, e, x[stk[a]]), area(d, e, x[stk[a + 1]])) < 0) a = a + 1 >= top ? 0 : a + 1;
        while (cmp(proj(d, e, x[stk[b]]), proj(d, e, x[stk[b + 1]])) < 0) b = b + 1 >= top ? 0 : b + 1;
        if (!i) c = a;
        while (cmp(proj(d, e, x[stk[c]]), proj(d, e, x[stk[c + 1]])) > 0) c = c + 1 >= top ? 0 : c + 1;
        PDD ta = x[stk[a]], tb = x[stk[b]], tc = x[stk[c]];
        DB h = area(d, e, ta) / mo(e - d);
        DB w = proj(d, e, tb) - proj(d, e, tc);
        if (cmp(w * h, ans) < 0)
        {
            ans = w * h;
            as[0]= d + norm(e - d) * proj(d, e, tb);
            as[3] = d + norm(e - d) * proj(d, e, tc);
            PDD u = norm(rot(e - d, -M_PI / 2));
            as[1] = as[0]+ u * h;
            as[2] = as[3] + u * h;
        }
    }
}
int main()
{
    int n, k = 0;
    PDD a[N];
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%lf %lf", &a[i].fi, &a[i].se);
    convex(a, n), rotcal(a, n);
    for (int i = 1; i < 4; ++i) if (cmp(as[i].se, as[k].se) < 0 || (!cmp(as[i].se, as[k].se) && cmp(as[i].fi, as[k].fi) < 0)) k = i;
    printf("%.5lf\n", ans);
    for (int i = 0; i < 4; ++i, k = k + 1 >= 4 ? 0 : k + 1)
    {
        if (!cmp(as[k].fi, 0)) as[k].fi = 0;
        if (!cmp(as[k].se, 0)) as[k].se = 0;
        printf("%.5lf %.5lf\n", as[k].fi, as[k].se);
    }
    return 0;
}

例题二

[WFOI - 01] 循环节（circle）

有 blog 就不讲了