平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。
如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。
请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。
平面内有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。
2 0 90 0 90 100 200 100 200
2
//用例数字太大……只能这么土了,一不小心就bad_alloc
#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
using namespace std;
struct pt
{
long x1,x2;
long y1,y2;
pt(long _x1,long _y1,long _x2,long _y2):x1(_x1),y1(_y1),x2(_x2),y2(_y2){};
};
int main()
{
int n;
while(cin>>n)
{
long x1,y1,x2,y2;
vector<long> xs(2*n);
vector<long> ys(2*n);
vector<pt> co;
for(int i=0;i<n;i++)
co.push_back(pt(0,0,0,0));
for(int i=0;i<n;i++)
{
cin>>xs[i];
co[i].x1=xs[i];
}
for(int i=0;i<n;i++)
{
cin>>ys[i];
co[i].y1=ys[i];
}
for(int i=0;i<n;i++)
{
cin>>xs[i+n];
co[i].x2=xs[i+n];
}
for(int i=0;i<n;i++)
{
cin>>ys[i+n];
co[i].y2=ys[i+n];
}
int out=0;
for(int i=0;i<2*n;i++)
{
for(int j=0;j<2*n;j++)
{
int cnt=0;
for(int p=0;p<n;p++)
{
if(co[p].x1<=xs[i]&&co[p].x2>xs[i]&&
co[p].y1<=ys[j]&&co[p].y2>ys[j])
cnt++;
}
out=max(out,cnt);
}
}
cout<<out<<endl;
}
}