算法题：uva 1382

题目链接

1. 坐标值比较大，所以离散化坐标

2. 坐标的绝对值不超过10^9，说明可能有负数，所以把 全部坐标移动转换为正数（加上10^9）

3. mat[i][j] ，表示（0,0） （i, j）为对顶点矩形之 内包括边界上有多少个点。

4. 枚举矩形的上下界，然后选择左右边界。 对于确定的左边界left 和右边界right， 假设是下图的R3是left,  L3是right，那么数量为：

L1 + L2 + L3 - (R1+R2) + R3.

为了要使得以L3为右边界的矩形上的点最多，那么应该使得 R3-(R1+R2)的值最 大。

所以，枚举右边界j， 维护保存j左边的R3-(R1+R2)的最大值，只要O(n)就可以确定答案了 。

5. 需要注意的是所有点 可能都在同一条直线上，所以给横坐标和右坐标都另外添加一个点

代码：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;  

const int MAXN = 110;
const int ADD  = 1e9+10;
int n;
int arr[MAXN][2];
int mat[MAXN][MAXN];
int X[MAXN], Y[MAXN], row, col;  

inline int findID(int* A, int len, int x){
    return lower_bound(A, A+len, x)-A+1;
}  

inline void input(){
    row = 1, col = 1;
    X[0] = Y[0] = 0;  

    for(int i=0; i<n; ++i){
        scanf("%d%d", &arr[i][0], &arr[i][1]);
        X[row++] = arr[i][0] += ADD;
        Y[col++] = arr[i][1] += ADD;
    }
    sort(X, X+row);
    row = unique(X, X+row)-X;  

    sort(Y, Y+col);
    col = unique(Y, Y+col)-Y;  

    memset(mat, 0, sizeof(mat));
    for(int i=0; i<n; ++i){
        int a = findID(X, row, arr[i][0]);
        int b = findID(Y, col, arr[i][1]);
        mat[a][b] = 1;
    }
    for(int i=1; i<=row; ++i){
        for(int j=1; j<=col; ++j)
            mat[i][j] += mat[i][j-1]+mat[i-1][j]-mat[i-1][j-1];
    }
}  

inline int solve(){  

    int ans = 1;
    // 枚举上下界
    for(int up=1; up<row; ++up){
        for(int down=up+1; down<=row; ++down){  

            int maxx = mat[down][1]-mat[up-1][1];  

            for(int i=2; i<=col; ++i){
                int right = mat[down][i]-mat[down-1][i]
                          + mat[up][i]-mat[up-1][i]
                          + mat[down-1][i]-mat[up][i]
                          - (mat[down-1][i-1]-mat[up][i-1]);
                ans = max(ans, right+maxx);  

                int tmp = mat[down][i]-mat[up-1][i]
                        - (mat[down][i-1]-mat[up-1][i-1]);  

                tmp -= mat[down][i]-mat[down-1][i]
                     + mat[up][i]-mat[up-1][i];  

                if(tmp > maxx) maxx=tmp;  

            }  

        }
    }
    return ans;
}  

int main(){  

    int cas=1;  

    while(~scanf("%d", &n) && n){  

        input();
        printf("Case %d: %d\n", cas++, solve());  

    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， mat
， 坐标
， 矩形
， 离散的点
边界
13、1382日元、1382年、138、g1382，以便于您获取更多的相关知识。