[HNOI 2007] 最小矩形覆盖

题目大意

给定 nn 个平面上的点,求覆盖它们的面积最小的矩形。输出矩形面积,yy 坐标最小,相同时 xx 最小的点开始逆时针输出矩形的顶点。

3n50,0003 \leqslant n \leqslant 50,000

题目链接

【HNOI 2007】最小矩形覆盖 - Luogu 3187

题解

凸包 + 旋转卡壳。

首先,答案矩形的一条边一定经过凸包的相邻两点,剩下的三条边也各经过一个点(可能重复)。于是,我们可以枚举第一个顶点,也就是经过两个点的那条边,剩下三个点用类似旋转卡壳的方法求出并跟着更新,可以用各种乱搞的方法求出当前的矩形。

不过,一定要记得点的输出顺序,我 WA 了好几遍后才看见那句话,还以为是自己求矩形的方法精度炸了。。。(不过最后懒地该回去了。。。是用点在直线上的投影求得矩形的四个顶点)

一共 WA 了八次吧。。。捣鼓了一整天。。。

写完一测样例,以为自己的精度炸了,小数点后第一位就错了,后来发现是自己样例打错了 23333

之后在以为精度继续炸的时候,改用了 long double ,可仍然 WA ,甚至在写了正确的输出顺序时也是。后来改回了 double 后就 AC 了。。。

代码

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <cstdio>
#include <cfloat>
#include <cmath>
#include <algorithm>
// #define DBG
const int MAXN = 50005;
const double EPS = 1e-9;
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
void print() {
if (fabs(x) <= EPS) x = 0;
if (fabs(y) <= EPS) y = 0;
printf("%.5lf %.5lf\n", x, y);
}
Point getPerpendicular() {
double X = sqrt(1 / (1 + (x / y) * (x / y)));
int sx, sy;
if (x > 0 && y > 0) sx = 1, sy = -1;
else if (x > 0 && y <= 0) sx = 1, sy = 1;
else if (x <= 0 && y > 0) sx = -1, sy = -1;
else sx = 1, sy = -1;
return Point(sx * X, sy * sqrt(1 - X * X));
}
bool operator<(const Point &another) const {
return x < another.x || (x == another.x && y < another.y);
}
friend Point operator+(const Point &a, const Point &b) {
return Point(a.x + b.x, a.y + b.y);
}
friend Point operator-(const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend Point operator*(const Point &p, const double a) {
return Point(p.x * a, p.y * a);
}
friend Point operator/(const Point &p, const double a) {
return Point(p.x / a, p.y / a);
}
friend double dot(const Point &a, const Point &b) {
return a.x * b.x + a.y * b.y;
}
friend double cross(const Point &a, const Point &b) {
return a.x * b.y - a.y * b.x;
}
friend double dist(const Point &a, const Point &b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
} P[MAXN], ch[MAXN];
struct Rectangle {
Point p[4];
void print() {
int temp = 0;
for (int i = 1; i < 4; i++)
if (p[i].y < p[temp].y || (p[i].y == p[temp].y && p[i].x < p[temp].x)) temp = i;
for (int i = 0; i < 4; i++) p[(i + temp) % 4].print();
}
Point &operator[](int i) {
return p[i];
}
};
int getConvexHell(int n) {
std::sort(P + 1, P + n + 1);
int m = 0;
for (int i = 1; i <= n; i++) {
while (m > 1 && cross(ch[m - 1] - ch[m - 2], P[i] - ch[m - 2]) <= 0) m--;
ch[m++] = P[i];
}
int k = m;
for (int i = n; i; i--) {
while (m > k && cross(ch[m - 1] - ch[m - 2], P[i] - ch[m - 2]) <= 0) m--;
ch[m++] = P[i];
}
m > 1 ? m-- : 0;
return m;
}
Rectangle ans;
double ansArea = DBL_MAX;
void rotatingCalipers(int n) {
for (int curr = 0, right = 1, up = 1, left = 1; curr < n; curr++) {
while (dot(ch[curr + 1] - ch[curr], ch[right + 1] - ch[right]) >= 0) right = (right + 1) % n;
curr ? 0 : up = right;
while (cross(ch[curr + 1] - ch[curr], ch[up + 1] - ch[up]) >= 0) up = (up + 1) % n;
curr ? 0 : left = up;
while (dot(ch[curr + 1] - ch[curr], ch[left + 1] - ch[left]) <= 0) left = (left + 1) % n;
Point currV = ch[curr + 1] - ch[curr];
double currLen = dist(ch[curr], ch[curr + 1]);
double height = fabs(cross(currV, ch[up] - ch[curr]) / currLen);
double bottom = fabs(dot(currV, ch[left] - ch[curr]) / currLen)
+ fabs(dot(currV, ch[right] - ch[curr]) / currLen);
double currArea = bottom * height;
Point currPerpendicular = currV.getPerpendicular();
if (currArea < ansArea) {
ansArea = currArea;
ans[0] = ch[curr] + currV * fabs((dot(currV, ch[right] - ch[curr])) / currLen) / currLen;
ans[1] = ans[0] + currPerpendicular * height;
ans[2] = ans[1] - currV * bottom / currLen;
ans[3] = ans[2] - currPerpendicular * height;
}
}
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lf %lf", &P[i].x, &P[i].y);
int m = getConvexHell(n);
rotatingCalipers(m);
printf("%.5lf\n", ansArea);
ans.print();
return 0;
}