算法题：uva 1312

题目大意：

在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\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://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， 图论 离散数学 算法
， 坐标
， 离散数据
， 离散
， 矩形
边界
g1312、hp1312、131、1312什么意思、1312轴承，以便于您获取更多的相关知识。