矩形重叠

题目难度：三星
考察点：枚举、几何

方法：枚举

1. 分析：
   注意一点题目要求的是平面内重叠矩形数量最多的地方,有多少个矩形相互重叠？那么对于这个题目来说，正常的循环遍历方法是无法轻易解决的，那么我们换种方法，我们想办法将这n个矩形所包含的点全部枚举出来，然后在检查看有多少个矩形包含这个点，输出包含点最多的矩形个数值即可。
   举个例子:现在有两个矩形，第一个矩形的左下角坐标为(0,0)右上角坐标为(6,6)，第二个矩形的左下角坐标为(5,5)右上角坐标为(10,10)，那么我们将这两个矩形所包含的点列举出来：{(0,0),(0,5),(0,6),(0,10),(5,0),(5,5),(5,6),(5,10),(6,0),(6,5),(6,6),(6,10),(10,0),(10,5),(10,6),(10,10)} 一共16个点，然后就枚举这16个点，对于第i个点来说，看一下到底有多少个矩形包含这个点，记录包含矩形的个数，最后取最大值。

算法实现：首先我们要获取n个矩形可能包含的点，那么我们将所有的x坐标列出来，所有的y坐标列出来，那么所包含的点(x,y)也就随之列举出来了，一共是2n*2n个点，然后对于这个点我们判断在n个矩形中到底有多少个矩形包含(x,y)坐标点，判断的方式为：如果满足条件，那么(x,y)就属于以(x1,y1)为左下角，(x2,y2)为右上角的矩形，记录结果加一，遍历n遍以后，比较最大值输出即可。

Tips：矩形A与矩形B重叠，矩形B与矩形C重叠，但是不意味着矩形A与矩形C也重叠。
2. 复杂度分析：
时间复杂度：O(n^3)
空间复杂度：O(n)

3. 代码：

   #include <iostream>
   using namespace std;
   typedef long long LL;
   struct Node
   {
    int x1, y1, x2, y2;
   }a[55];
   int x[150], y[150];
   int main()
   {
    int n;
    while(cin>>n)
    {
        int cntx = 0, cnty = 0;
        for(int i=0; i<n; i++)
        {
            cin>>a[i].x1;
            x[cntx++] = a[i].x1;
        }
        for(int i=0; i<n; i++)
        {
            cin>>a[i].y1;
            y[cnty++] = a[i].y1;
        }
        for(int i=0; i<n; i++)
        {
            cin>>a[i].x2;
            x[cntx++] = a[i].x2;
        }
        for(int i=0; i<n; i++)
        {
            cin>>a[i].y2;
            y[cnty++] = a[i].y2;
        }
        int ans = 0;
        for(int i=0; i<cntx; i++)
        {
            for(int j=0; j<cnty; j++)
            {
                int sum = 0;
                for(int k=0; k<n; k++)
                {
                    if(x[i]>=a[k].x1&&y[j]>=a[k].y1 && x[i]<a[k].x2&&y[j]<a[k].y2) sum++;
                }
                ans = max(ans, sum);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
   }