UVa 1312 Cricket Field【暴力】

本文主要是介绍UVa 1312 Cricket Field【暴力】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

传送门

一个w*h（1<=w,h<=10000）的网格里面有n(0<=n<=100)棵树，要求找出一个最大的空正方形。

样例

input

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

output

4 3 4

解释

这个最大的空正方形坐标为4 3，长度为4。

思路

要求的是正方形，其实就是矩形，最后判断的时候取长和宽的较小值即可。
数的数量最多只有100，所以可以使用有技巧的暴力。

1. 对所有的点按照y值进行排序，记作dy。
2. 对所有的点按照x值进行排序，记作node。
3. miny和maxy为的纵坐标的区间值，则目前区间的纵坐标区域为[miny,maxy]。
4. 对所有的点按照x的大小进行一个排序。判断输入的所有的点的y值在不在区间[miny,maxy]内。
5. 比较判断：miny作为空正方形的左下角点的y坐标，node[k].x作为空正方形的左下角的x坐标。

总体复杂度最多位O(n^3)，n为100。

代码

#include<cstdio>
#include<map>
#include<queue>
#include<cstring>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include <math.h>
#include <stack>
using namespace std;
const int maxn = 105;
struct Node
{int x,y;
} node[maxn];int dy[maxn];bool cmp(Node a,Node b)
{if (a.x == b.x) return a.y<b.y;else return a.x < b.x;
}int main()
{int CaseNum;scanf("%d",&CaseNum);while(CaseNum--){int W,H,N;scanf("%d%d%d",&N,&W,&H);for(int i=0; i<N; i++) scanf("%d%d",&node[i].x,&node[i].y),dy[i]=node[i].y;dy[N] = H;dy[N+1] = 0;sort(dy,dy+N+2);sort(node,node+N,cmp);int uni_y = unique(dy,dy+N+2) - dy;int ansx,ansy,ans=0;for(int i=0; i<uni_y; i++){for(int j=i+1; j<uni_y; j++){int maxy = dy[j];int miny = dy[i];int hh = maxy - miny;//高int ww = 0;//宽int tmp = 0;//左边界for(int k = 0; k < N; k++){if(node[k].y >= maxy || node[k].y <= miny ) continue;ww = node[k].x - tmp;if(ans<min(ww,hh)){ans = min(ww,hh);ansx = tmp;ansy = miny;}tmp =  node[k].x;}ww = W - tmp;//最右的边也计算一下if(ans<min(ww,hh)){ans = min(ww,hh);ansx = tmp;ansy = miny;}}}printf("%d %d %d\n",ansx,ansy,ans);if(CaseNum) printf("\n");}}
/*
Sample Input
2
7  10  7
3  2
4  2
7  0
7  3
4  5
2  4
1  7
5 6 6
1 1
2 2
3 3
4 4
5 5
Sample Output
4  3  42 0 3
*/

Hit

在对y值进行排序的时候，可以将0和H这两个值加进y中，这个时候y的区间就会完整，会考虑到0和H，而不是只有点的纵坐标了。
只要暴力得当，使用有技巧的暴力还是可以的。

这篇关于UVa 1312 Cricket Field【暴力】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---