算法题：uva 1312 - Cricket Field.

算法题：uva 1312 - Cricket Field.2014-03-17 csdn博客 shuangde800题目大意：

在w*h的坐标上给n个点，然后求一个最大的矩形，使得这个矩形内（不包括边界）没有点，注意边界上是可以有点的。

首先要把这些坐标进行离散化，离散话时要注意一点，如果有两个点原来坐标不是相邻的，但是离散化以后却变成相邻了，这时候要在它们之间加上一个点。

预处理后，枚举矩形上下界，然后再用O（n）的复杂度找出左右边界。

代码：

#include<iostream>#include<cstdio>#include<algorithm>#include<cctype>#include<cstring>using namespace std;const int MAXN = 120;int n,w,h;int row, col;int d[MAXN];int arr[MAXN][2];int x[MAXN], y[MAXN];int idx[10010], idy[10010];int mat[MAXN][MAXN];inline void input（）{x[0] = y[0] = 0;row= col= 1;// 输入并离散化for（int i=0; i<n; ++i）{scanf（"%d%d", &arr[i][0], &arr[i][1]）;x[row++] = arr[i][0];y[col++] = arr[i][1];}x[row++] = w;y[col++] = h;sort（x, x+row）;sort（y, y+col）;row = unique（x, x+row） - x;col = unique（y, y+col） - y;int end = row;for（int i=1; i<end; ++i）if（x[i] ！= x[i-1]+1）{ x[row++] = x[i-1] + 1;}end = col; for（int i=1; i<end; ++i）if（y[i] ！= y[i-1]+1）{y[col++] = y[i-1] + 1;}sort（x, x+row）;sort（y, y+col）;for（int i=0; i<row; ++i）idx[x[i]] = i;for（int i=0; i<col; ++i）idy[y[i]] = i;memset（mat, 0, sizeof（mat））;for（int i=0; i<n; ++i）{int a = idx[arr[i][0]];int b = idy[arr[i][1]];mat[a][b] = 1;}for（int i=0; i<row; ++i）{for（int j=0; j<col; ++j）{if（i==0） mat[i][j] += mat[i][j-1];else if（j==0） mat[i][j] += mat[i-1][j];else mat[i][j] += mat[i][j-1] + mat[i-1][j] - mat[i-1][j-1];}}}inline void solve（）{int maxLen=1, max_x=0, max_y=0;int xx, yy;for（int low=0; low<row-1; ++low）{for（int up=low+1; up<row; ++up）{memset（d, 0, sizeof（d））;for（int j=0; j<col; ++j）{int tmp;if（j>0）{tmp = mat[up][j]-mat[low][j]- （mat[up][j-1]-mat[low][j-1]）;}else{tmp = mat[up][j]-mat[low][j];}if（tmp == 0）{d[j] = d[j-1] + 1;int low_x = max（low, 0）;int low_y = max（j-d[j], 0）;int up_x= min（row-1, up+1）;int up_y= min（col-1, j+1）;int hh = x[up_x] - x[low_x];int ww = y[up_y] - y[low_y];int ll = min（hh, ww）;if（ll > maxLen）{maxLen = ll;max_x = low_x;max_y = low_y;xx = up_x;yy = up_y;}}}}}printf（"%d %d %d
", x[max_x], y[max_y], maxLen）;}int main（）{int nCase;bool first=true;scanf（"%d", &nCase）;while（nCase--）{scanf（"%d%d%d", &n, &w, &h）;first ？ first=false : putchar（"
"）;if（n==0）{printf（"%d %d %d
",0,0,min（w,h））;continue;}input（）;solve（）;}return 0;}