解題區/解題區 - UVa

UVa 1312 - Cricket Field

contents

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

Problem

在網格中，找一個最大空白正方形。

Sample Input

1
2
3
4
5
6
7
8
9
10
1
7 10 7
3 2
4 2
7 0
7 3
4 5
2 4
1 7

Sample Output

1
4 3 4

Solution

其實就類似找最大空白矩形中的特例，取寬高最小的即可。

算法主要是排序所有平面上的點後，窮舉底部的一點，往垂直方向掃描收束。對兩個軸都要做一次。

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
#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, n;
        scanf("%d %d %d", &n, &h, &w);
        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 P = 0, Q = 0, L = 0;
        for (int i = 0; i < n; i++) {
            int mny = 0, mxy = w;
            for (int j = i+1; j < n; j++) {
                int l = min(tree[j].x-tree[i].x, mxy-mny);
                if (l > L)
                    P = tree[i].x, Q = mny, L = l;
                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 (int i = 0; i < n; i++) {
            int mnx = 0, mxx = h;
            for (int j = i+1; j < n; j++) {
                int l = min(tree[j].y-tree[i].y, mxx-mnx);
                if (l > L)
                    P = mnx, Q = tree[i].y, L = l;
                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);
            }
        }
        if (cases++)    puts("");
        printf("%d %d %d\n", P, Q, L);
    }
    return 0;
}