矩形重疊--矩形重疊個數問題

平面内有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:

#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;
}