UVa 1312 - Cricket Field

#思维 #扫描法
Published on 2016-02-03

题目地址

描述

在 W×H(W,H≤10000)W \times H(W, H \le 10000) 的网格中有 n(n≤100)n(n\le100) 个点，请你找出一个最大的正方形，使得内部不包含任何点。输出这个正方形的边长以及左下角点的坐标。

样例输入

1

7 10 7
3 2
4 2
7 0
7 3
4 5
2 4
1 7

样例输出

4 3 4

分析

与 UVa 1382 - Distant Galaxy 很像，可以知道这个正方形必定有三个边有点（假如我们考虑边界上布满了点的话）。
所以枚举上下边界经过的点，然后再看上下边界内的点的横坐标之间最大的空隙是多少（注意假设左右边界上有点），然后计算更新答案即可。复杂度 O(n3)O(n^3)。
不必质疑，「枚举上下边界经过的点」说法的确不严谨，因为很可能正方形大小被横坐标限制住了，导致无法达到上下边界，但这个算法是肯定正确的。如果不好理解的话，请考虑我们就是找最大的矩形，然后把它削成正方形。

代码

//  Created by Sengxian on 2/3/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1312 扫描法 KISS
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n')
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(isdigit(ch));
    return n;
}

const int maxn = 100 + 3;
struct Point {
    int x, y;
    bool operator < (const Point &p) const {
        return x < p.x;
    }
}p[maxn];

int n, w, h;
vector<int> ys;

void Solve() {
    int l = 0; Point ans = (Point){0, 0};
    //枚举上下边界
    for(int i = 0; i < ys.size(); ++i)
        for(int j = i + 1; j < ys.size(); ++j) {
            int ymin = ys[i], ymax = ys[j], mX = 0, x = 0, lastX = 0;
            for(int k = 0; k < n; ++k) //找到在上下边界内最大的空隙 mX
                if(p[k].y > ymin && p[k].y < ymax) {
                    if(p[k].x - lastX > mX)
                        mX = p[k].x - lastX, x = lastX;
                    lastX = p[k].x;    
                }
            if(w - lastX > mX) mX = w - lastX, x = lastX;
            int _l = min(mX, ymax - ymin);
            if(_l > l) ans = (Point){x, ymin}, l = _l;
        }
    printf("%d %d %d\n", ans.x, ans.y, l);
}


int main() {
    int caseNum = ReadInt();
    while(caseNum--) {
        n = ReadInt(), w = ReadInt(), h = ReadInt();
        ys.clear(); ys.push_back(0); ys.push_back(h);
        for(int i = 0; i < n; ++i) 
            p[i].x = ReadInt(), ys.push_back(p[i].y = ReadInt());
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        sort(p, p + n);
        Solve();
        if(caseNum) br;
    }
    return 0;
}

附加输入

5

7 10 7
3 2
4 2
7 0
7 3
4 5
2 4
1 7

7 10 7
3 2
4 2
7 0
7 3
4 5
2 4
1 7

1 90 100
51 19

74 100 38
4 32
65 14
12 0
24 24
83 1
3 24
64 21
54 21
79 15
1 14
26 21
20 34
39 3
83 31
99 3
38 16
78 8
85 14
32 11
38 7
47 32
87 15
6 26
17 16
78 22
45 7
78 3
30 9
37 9
7 22
47 8
91 30
31 25
2 6
91 24
58 18
25 19
54 16
34 32
66 26
64 6
59 1
0 18
59 1
52 4
52 26
69 1
53 22
37 7
90 33
32 9
34 36
40 8
66 7
33 5
99 25
38 35
83 7
82 10
20 33
54 5
1 37
55 29
9 32
54 35
93 15
66 37
9 0
1 15
26 31
63 24
15 1
52 16
73 6

25 2 91
1 28
0 40
0 62
0 41
0 30
1 75
1 81
0 16
1 55
1 31
1 10
1 72
1 13
0 40
0 2
1 49
1 64
1 23
0 15
0 17
0 17
0 21
0 73
0 11
0 59

附加输出

4 3 4

4 3 4

0 19 81

1 6 16

0 0 2
UVa 1394 - And Then There Was One