笔试刷题-网易2018-06-07

题目描述：

/**
平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。

如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。

请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。


输入描述:
输入包括五行。
第一行包括一个整数n(2 <= n <= 50), 表示矩形的个数。
第二行包括n个整数x1[i](-10^9 <= x1[i] <= 10^9),表示左下角的横坐标。
第三行包括n个整数y1[i](-10^9 <= y1[i] <= 10^9),表示左下角的纵坐标。
第四行包括n个整数x2[i](-10^9 <= x2[i] <= 10^9),表示右上角的横坐标。
第五行包括n个整数y2[i](-10^9 <= y2[i] <= 10^9),表示右上角的纵坐标。


输出描述:
输出一个正整数, 表示最多的地方有多少个矩形相互重叠,如果矩形都不互相重叠,输出1。

输入例子1:
2
0 90
0 90
100 200
100 200

输出例子1:
2

*/

思路如下：

离散化
对于一个d维度立方体由于点是有限点，可以构成一个大的网格图
比如以2d为例，此题目输入有x轴，y轴上的点，
那么有x1 x2 x3...xs个不同的值
有y1,y2,y3,...yt个不同的值
那么以这里画出st个点位个点画出一个网格
那么题目中输入的矩形的左下角和右上角一定在这样st个个点当中
那么其实要穷举的可能性有多少呢？
有st个穷举这st个个点各自最多包含于多少个矩形中即可算出矩形重叠最多的地方，堆叠多少个矩形
为什么是穷举st个即可？
因为这样的矩形格点图，矩形间只能共同覆盖st个格点或者格点之间连线上的点
那么只要再证明格点连线上的点（除去格点）有m个矩形覆盖
那么这个在线上的点一定会和其端点的其中一个覆盖的情况一样，由于矩形都是从格点构成的，所以
只要枚举s*t个个点即可
代码如下：

#include<stdio.h>
#include<iostream>
#include<set>

#define MAX_N 55

using namespace std;

//这里假设题目给出的输入的矩形 左下角和右上角都是合法，而且该矩形为面积大于0不是退化成线
int x1[MAX_N], y1[MAX_N], x2[MAX_N], y2[MAX_N];
set<int> xSet, ySet;

int main()
{
    int N, res=1;
    scanf("%d", &N);
    for(int i=0; i<N; i++)
    {
        scanf("%d", x1+i);
        xSet.insert(x1[i]);
    }

    for(int i=0; i<N; i++)
    {
        scanf("%d", y1+i);
        ySet.insert(y1[i]);
    }

    for(int i=0; i<N; i++)
    {
        scanf("%d", x2+i);
        xSet.insert(x2[i]);
    }


    for(int i=0; i<N; i++)
    {
        scanf("%d", y2+i);
        ySet.insert(y2[i]);
    }
    for(set<int>::iterator xIt=xSet.begin(); xIt!=xSet.end(); xIt++){
        for(set<int>::iterator yIt=ySet.begin(); yIt!=ySet.end(); yIt++){
            int cnt=0, x=(*xIt), y=(*yIt);
            for(int i=0; i<N; i++){
                //这里不能同时>= <=要防止边界 题目要求边界不算如
                //这样可以避免把一个点刚好是一个个矩形的右上，是另外一个矩形的左下
                //这样这个点只会被右上的时候计算一次，然后避免重复计算
                if(x>x1[i] && x<=x2[i] && y>y1[i] && y<=y2[i])
                    cnt++;
            }
            if(cnt>res)
                res=cnt;
        }
    }
    printf("%d",res);
    return 0;
}