UVa 1312 – Cricket Field [枚举]

Link

点击打开题目链接

Problem

Once upon a time there was a greedy King who ordered his chief Architect to build a field for royal cricket inside his park. The King was so greedy, that he would not listen to his Architect’s proposals to build a field right in the park center with pleasant patterns of trees specially planted around and beautiful walks inside tree alleys for spectators. Instead, he ordered neither to cut nor to plant even a single tree in his park, but demanded to build the largest possible cricket field for his pleasure. If the Kind finds that the Architect has dared to touch even a single tree in his park or designed a smaller field that it was possible, then the Architect will loose his head. Moreover, he demanded his Architect to introduce at once a plan of the field with its exact location and size.

Your task is to help poor Architect to save his head, by writing a program that will find the maximum possible size of the cricket field and its location inside the park to satisfy King’s requirements.

The task is somewhat simplified by the fact, that King’s park has a rectangular shape and is situated on a flat ground. Moreover, park’s borders are perfectly aligned with North-South and East-West lines. At the same time, royal cricket is always played on a square field that is also aligned with North-South and East-West lines. Architect has already established a Cartesian coordinate system and has precisely measured the coordinates of every tree. This coordinate system is, of course, aligned with North-South and East-West lines. Southwestern corner of the park has coordinates (0, 0) and Northeastern corner of the part has coordinates (W, H), where W and H are the park width and height in feet respectively.

For this task, you may neglect the diameter of the trees. Trees cannot be inside the cricket field, but may be situated on its side. The cricket field may also touch park’s border, but shall not lie outside the park.

Mean

在一个W*H的棋盘上有N个点,让你找出一个最大的“正方形”,正方形内部不能含有点。

Analysis

首先想到枚举每个内部不含点的矩形,有了所有的矩形,也就有了最大的正方形。

枚举矩形时可以考虑枚举矩形的左右边X1、X2,然后得出X1-X2内部所有的点的Y坐标,以这些Y坐标为分隔,将X1-X2分割成若干矩形,这样就枚举出来了。

纪录所有的Y坐标,可以边枚举边纪录,同时用set方便去重。

Code

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int n, w, h;
int p, q, l;
vector<P> pt;

void init() {
    scanf("%d%d%d", &n, &w, &h);
    pt.clear();
    pt.push_back(P(0, 0));
    pt.push_back(P(w, h));
    for(int i = 0; i < n; ++i) {
        P p; scanf("%d%d", &p.first, &p.second);
        pt.push_back(p);
    }
    sort(pt.begin(), pt.end());
    p = q = l = 0;
}

void update(int lx, int rx, set<int> & y) {
    int dx = rx - lx;
    int pre = 0;
    for(auto it = ++y.begin(); it != y.end(); ++it) {
        int L = min(dx, *it - pre);
        if(L > l) {
            l = L, p = lx, q = pre;
        }
        pre = *it;
    }
}

void solve() {
    for(int i = 0; i < pt.size(); ++i) {
        if(i && pt[i].first == pt[i-1].first) continue;
        set<int> ally{0, h};
        for(int j = i + 1; j < pt.size(); ++j) {
            if(pt[j].first == pt[i].first) continue;
            if(pt[j].first != pt[j-1].first) {
                update(pt[i].first, pt[j].first, ally);
            }
            ally.insert(pt[j].second);
        }
    }
}

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        init();
        solve();
        printf("%d %d %d\n", p, q, l);
        if(T) puts("");
    }
    return 0;
}

欢迎留言