解題區/解題區 - UVa

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;
}