「BZOJ1185」[HNOI2007]最小矩形覆盖

Description

给定一些点的坐标,要求求能够覆盖所有点的最小面积的矩形,
输出所求矩形的面积和四个顶点坐标

Input

第一行为一个整数nn(3<=n<=50000)
从第22至第n+1n+1行每行有两个浮点数,表示一个顶点的xxyy坐标,不用科学计数法

Output

第一行为一个浮点数,表示所求矩形的面积(精确到小数点后55位),
接下来44行每行表示一个顶点坐标,要求第一行为yy坐标最小的顶点,
其后按逆时针输出顶点坐标.如果用相同yy坐标,先输出最小x坐标的顶点

Sample Input

1
2
3
4
5
6
6 1.0 3.00000
1 4.00000
2.0000 1
3 0.0000
3.00000 6
6.0 3.0

Sample Output

1
2
3
4
5
18.00000
3.00000 0.00000
6.00000 3.00000
3.00000 6.00000
0.00000 3.00000

Solution

矩形的一条边经过的直线一定经过凸包上一条边。
枚举凸包一条边,找到最左点和最右点和最上点(相对于这条边),卡壳的方法时间复杂度是O(n2)O(n^2)
注意计算的时候有可能会出现点重复了,导致交点无法求,所以要以枚举的这条边做逆时针0,90,180,2700^\circ,90^\circ,180^\circ,270^\circ和上面求的三个点求交。
注意要把重复的点去掉了。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 61000;

struct Vec {
double x, y;
Vec() {}
Vec(double _x, double _y) {x = _x, y = _y;}
Vec operator *(double k) {return Vec(x * k, y * k);}
Vec operator /(double k) {return Vec(x / k, y / k);}
double d() {return sqrt(x*x+y*y);}
};
Vec operator +(Vec a, Vec b) {return Vec(a.x + b.x, a.y + b.y);}
Vec operator -(Vec a, Vec b) {return Vec(a.x - b.x, a.y - b.y);}
double dot(Vec a, Vec b) {return a.x * b.x + a.y * b.y;}
double cross(Vec a, Vec b) {return a.x * b.y - a.y * b.x;}
typedef Vec Pt;

Pt a[N], b[N];
#define eps 1e-8
bool cmp(Pt x, Pt y) {
double v = cross(x - a[1], y - a[1]);
if(fabs(v) < eps) return x.x < y.x;
return v > eps;
}
int n;
int st[N], top, tot;
void tubao() {
st[++top] = 1;
st[++top] = 2;
for(int i = 3; i <= n; ++i) {
while(top > 1 && cross(a[i] - a[st[top - 1]], a[st[top]] - a[st[top - 1]]) > eps) --top;
st[++top] = i;
}
tot = top;
for(int i = 0; i < tot; ++i) b[i] = a[st[i + 1]];
}
bool cmpx(Pt a, Pt b) {
if(fabs(a.y - b.y) > eps) return a.y - b.y < -eps;
return a.x - b.x < -eps;
}
Pt getins(Pt a, Pt b, Pt c) {
if(fabs(b.x - a.x) < eps)
return Pt(a.x, c.y);
double K = (b.y - a.y) / (b.x - a.x);
double B = a.y - K * a.x;
double K2 = -1/K;
double B2 = c.y - K2 * c.x;
double x = (B2 - B) / (K - K2);
double y = K2 * x + B2;
return Pt(x, y);
}
Pt get(Pt a, Pt b, Pt c) {
Vec ab = b - a;
double s = dot(b - a, c - a);
ab = ab * s / ab.d()/ab.d();
return a + ab;
}
Pt get2(Pt a, Pt b, Pt c) {
Vec ab = b - a;
swap(ab.x, ab.y);
ab.x = -ab.x;
double s = dot(ab, c - a);
ab = ab * s / ab.d() / ab.d();
return c - ab;
}
Pt res[5];
int main() {
freopen("1185.in","r",stdin);
freopen("1185.out","w",stdout);
n = read();
a[0].x = 1e100;
for(int i = 1;i <= n; ++i) {
scanf("%lf%lf",&a[i].x,&a[i].y);
if(a[i].x < a[1].x) swap(a[1], a[i]);
else if(fabs(a[i].x - a[1].x) < eps && a[i].y < a[1].y) swap(a[1], a[i]);
}
sort(a + 2, a + 1 + n, cmp);
int ttt = 0;
for(int i = 1; i <= n; ++i)
if(fabs(a[i].x - a[i - 1].x) < eps && fabs(a[i].y - a[i - 1].y) < eps) continue;
else a[++ttt] = a[i];
n = ttt;
tubao();
double ans = 1e99;
b[tot] = b[1];
int up = 2, lef = tot - 1, rig = 2;
Vec lx = b[1] - b[0];
while((lef - 1 + tot) % tot != 1) {
int nxt = (lef - 1 + tot) % tot;
Vec l1 = b[nxt] - b[lef];
if(dot(lx, l1) < -eps) lef = nxt;
else break;
}
for(int i = 1; i <= tot; ++i) {
/*if(fabs(b[i].x - b[i - 1].x ) < eps && fabs(b[i].y - b[i - 1].y) < eps) {
printf("i=%d\n", i);
break;
}*/
lx = b[i - 1] - b[i];
while((rig + 1) % tot != i - 1) {
int nxt = (rig + 1) % tot;
Vec l1 = b[nxt] - b[rig];
if(dot(lx, l1) <= eps) rig = nxt;
else break;
}
lx = b[i] - b[i - 1];
while((lef + 1) % tot != i - 1) {
int nxt = (lef + 1) % tot;
Vec l1 = b[lef] - b[nxt];
if(dot(lx, l1) >= -eps) lef = nxt;
else break;
}
lx = b[i] - b[i - 1];
while((up + 1) % tot != i - 1) {
int nxt = (up + 1) % tot;
double v1 = cross(lx, b[up] - b[i - 1]);
double v2 = cross(lx, b[nxt] - b[i - 1]);
if(v1 - v2 <= eps) up = nxt;
else break;
}
// printf("%d: (%d %d %d)\n", i, lef, rig, up);
// Pt p1 = getins(b[i], b[i - 1], b[rig]);
// Pt p2 = getins(b[rig], p1, b[up]);
//Pt p3 = getins(p2, b[up], b[lef]);
// Pt p4 = getins(b[i], b[i - 1], p3);
/*if(p4.x == 3 && p4.y == 3) {
printf("(%lf,%lf) (%lf,%lf) (%lf,%lf)\n", b[i].x,b[i].y,b[i-1].x,b[i-1].y,p1.x,p1.y);
printf("(%lf,%lf) (%lf,%lf) (%lf,%lf)\n", b[rig].x,b[rig].y,p1.x,p1.y,b[up].x, b[up].y);
printf("(%lf,%lf) (%lf,%lf) (%lf,%lf)\n", p2.x,p2.y,b[up].x,b[up].y,b[lef].x, b[lef].y);
printf("(%lf,%lf) (%lf,%lf) (%lf,%lf)\n", p3.x,p3.y,b[lef].x,b[lef].y,b[i-1].x, b[i-1].y);
printf("i=%d\n", i);
}*/
/*
Pt p1 = get(b[i - 1], b[i], b[rig]);
Pt p2 = get(p1, b[rig], b[up]);
Pt p3 = get(p2, b[up], b[lef]);
Pt p4 = get(p3, b[lef], b[i - 1]);
//如果有点重复就跪了
*/
Pt p1 = get2(b[i - 1], b[i], b[rig]);
Pt p2 = get2(p1, b[rig], b[up]);
Pt p3 = get2(p2, b[up], b[lef]);
Pt p4 = get2(p3, b[lef], b[i - 1]);
double area = cross(p1 - p4, p2 - p4);
if(area < ans) {
ans = area;
res[0] = p1;
res[1] = p2;
res[2] = p3;
res[3] = p4;
}
}
int tmp = 0;
for(int i = 0; i < 4; ++i) if(res[tmp].y > res[i].y) {
tmp = i;
}
else if(fabs(res[tmp].y - res[i].y) < eps && res[tmp].x > res[i].x) tmp = i;
printf("%.5lf\n", ans);
for(int i = 0; i < 4; ++i)
printf("%.5lf %.5lf\n", res[(i + tmp) % 4].x + eps, res[(i + tmp) % 4].y + eps);
return 0;
}