UVa 12830 - A Football Stadium

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在一個 L x W 的區域中,有 N 個點障礙物,要在其中找到一個最大空白矩形,中間不包含任何障礙物。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3
4 8
3
1 2
3 4
3 7
12 10
2
3 6
8 9
5 5
2
0 0
5 5

Sample Output

1
2
3
Case 1: 18
Case 2: 81
Case 3: 25

Solution

x, y 軸兩個都要做嘗試基底的動作。考慮一下都是 x = ? 當做基底時, 如果 y 值與窮舉點一樣, 那麼可選上或選下, 但無法決定哪個好,但是可以被決定於 y = ? 當做基底時的窮舉。整體效率是 O(n*n)

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
#include <stdio.h>
#include <algorithm>
using namespace std;
// same 10043 - Chainsaw Massacre.
struct Pt {
int x, y;
Pt(int a = 0, int b = 0):
x(a), y(b){}
bool operator<(const Pt &p) const {
if(p.x != x)
return x < p.x;
return y < p.y;
}
};
bool cmp(Pt a, Pt b) {
if(a.y != b.y)
return a.y < b.y;
return a.x < b.x;
}
Pt tree[3000];
int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while(testcase--) {
int h, w;
int x, y;
scanf("%d %d", &h, &w);
int op, i, j;
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d %d", &tree[i].x, &tree[i].y);
tree[n++] = Pt(0, 0);
tree[n++] = Pt(h, w);
tree[n++] = Pt(h, 0);
tree[n++] = Pt(0, w);
sort(tree, tree+n);
int area = 0;
for(i = 0; i < n; i++) {
int mny = 0, mxy = w;
for(j = i+1; j < n; j++) {
area = max(area, (tree[j].x-tree[i].x)*(mxy-mny));
if(tree[j].x == tree[i].x)
continue;
if(tree[j].y > tree[i].y)
mxy = min(mxy, tree[j].y);
else
mny = max(mny, tree[j].y);
}
}
sort(tree, tree+n, cmp);
for(i = 0; i < n; i++) {
int mnx = 0, mxx = h;
for(j = i+1; j < n; j++) {
area = max(area, (tree[j].y-tree[i].y)*(mxx-mnx));
if(tree[j].y == tree[i].y)
continue;
if(tree[j].x > tree[i].x)
mxx = min(mxx, tree[j].x);
else
mnx = max(mnx, tree[j].x);
}
}
printf("Case %d: %d\n", ++cases, area);
}
return 0;
}