本文共 1228 字，大约阅读时间需要 4 分钟。
题目大意：
在w*h的坐标上给n个点， 然后求一个最大的矩形，使得这个矩形内（不包括边界）没有点，注意边界上是可以有点的。
首先要把这些坐标进行离散化，离散话时要注意一点，如果有两个点原来坐标不是相邻的，但是离散化以后却变成相邻了，这时候要在它们之间加上一个点。
预处理后，枚举矩形上下界，然后再用O(n)的复杂度找出左右边界。
代码：
#include #include #include #include #include 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 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\n", 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('\n'); if(n==0){ printf("%d %d %d\n",0,0,min(w,h)); continue; } input(); solve(); } return 0;}
转载地址：http://lszni.baihongyu.com/