UVa 1312 球场（Cricket Field）

题意：
一个 W*H的网格里有n棵树，要求找一个最大空正方形。

分析：
树的棵数为 1~100个
如果遍历所有的树，每次枚举两个树之间的上下限，在从左到右枚举两个树之间的左右限，
需要O（n^4） 1e8数量的算法，会超时。
那么在从左到右枚举的时候可否优化呢。
答案是可以的。
如果前面的树的y不在枚举的两个树的上下限内部的话，那么不影响后续x
但是如果枚举的y在两个树的上下限内部的话，（不包括边界）那么会影响
这个时候及时更新枚举的y的树的x为左端点即可。
时间复杂度为O（n^3）
好在数据量很小，这个算法可以执行。

代码：

#include<bits/stdc++.h>
#define LL long long
#define ms(s) memset(s, 0, sizeof(s))
using namespace std;
int len;
int xx, yy;

struct Point {
    int x, y;
    Point(int x, int y):x(x), y(y) {}
    friend bool operator < (const Point &p1, const Point& p2) {
        return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x;
    }
    friend bool operator == (const Point& p1, const Point& p2) {
        return p1.x == p2.x && p1.y == p2.y;
    }
};

set<int> s; //y集合
vector<Point> vec;

void solve(int w) {
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(auto it1 = s.begin(); it1 != s.end(); ) {
        int ymin = *it1;
        for(auto it2 = ++it1; it2 != s.end(); it2++) {
            int ymax = *it2;
            int left = 0;
            for(auto p: vec) {
                if(p.y <= ymin || p.y >= ymax) {
                    continue;
                }
                if(len < min(ymax - ymin, p.x - left)) {
                    len = min(ymax - ymin, p.x - left);
                    xx = left;
                    yy = ymin;
                }
                left = p.x;
            }
            //考虑最后一个
            if(len < min(ymax - ymin, w - left)) {
                len = min(ymax - ymin, w - left);
                xx = left;
                yy = ymin;
            }
        }
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    int kase = 0;
    while(T--) {
        if(kase++) cout << endl;
        int N, W, H;
        int x, y;
        cin >> N >> W >> H;
        len = -1;
        vec.clear();
        s.clear();
        s.insert(0);
        s.insert(H);
        while(N--) {
            cin >> x >> y;
            s.insert(y);
            vec.push_back(Point(x, y));
        }
        solve(W);
        cout << xx << " " << yy << " " << len << endl;
    }
    return 0;
}