题目大意：在一个W ＊ H的网格中有n棵树，，要求你在这个网格中找出最大个的一个正方形，这个正方形内部不能有树，边上可以有树
解题思路：刚开始以为要暴力枚举每一个点，结果发现错了，其实这题就像UVA – 1382 Distant Galaxy这题一样，只不过这个是要找正方形，找正方形和找矩形类似，只需要取矩形的最小边就可以了
;#define maxn 110struct Point{int x, y;}p[maxn];int n, W, H, y[maxn];bool cmp(const Point a, const Point b) {if(a.x == b.x)return a.y < b.y;return a.x < b.x;}void init() {scanf(“%d%d%d”,&n, &W, &H);for(int i = 0; i < n; i++) {scanf(“%d%d”, &p[i].x, &p[i].y);y[i] = p[i].y;}y[n] = 0, y[n + 1] = H;sort(y, y + n + 2);sort(p, p + n, cmp);}void solve() {int ans = 0, xx, yy;int m = unique(y, y + n + 2) – y;for(int i = 0; i < m; i++)for(int j = i + 1; j < m; j++) {int h = y[j] – y[i], pre = 0, w;for(int k = 0; k < n; k++) {if(p[k].y <= y[i] || p[k].y >= y[j])continue;w = p[k].x – pre;if(ans < min(w, h)) {ans = min(w,h);xx = pre;yy = y[i];}pre = p[k].x;}w = W – pre;if(ans < min(h, w)) {ans = min(h,w);xx = pre;yy = y[i];}}printf(“%d %d %d\n”,xx, yy, ans);}int main() {int test;scanf(“%d”, &test);while(test–) {init();solve();if(test)printf(“\n”);}return 0;}
业精于勤，荒于嬉；行成于思，毁于随。
