矩形重叠（网易校招）

题目描述
平面内有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
输出
复制
2
思路：因为重叠的情况有很多，所以考虑不重叠的区域。如果否定这种情况，那么则满足该情况满足题意。题目数据量小，所以暴力出所有可能的情况，最后取最大值，注意情况需要考虑全，第 x 个矩形既可以作为第一个被重叠的矩形，也可以作为重叠的矩形。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct poi
{
ll x , y;
void print(int k)
{
if(k == 0) printf("左下角:");
else printf("右上角:");
printf("%lld %lld ",x,y);
}
};
struct rec
{
poi p[2];
int isnotinme(rec a)
{
return a.p[0].x >= p[1].x ||
a.p[1].y <= p[0].y ||
a.p[1].x <= p[0].x ||
a.p[0].y >= p[1].y;
}
};
int cnt[55];
rec Rec[55];
int main()
{
int n = 0;
int walk = 0;
int maxer = 0;
cin >> n;
for(int i = 0 ; i < 4 ; ++ i)
{
if(i == 2) walk ++;
for(int j = 0 ; j < n ; ++ j)
{
if(i % 2 == 0) scanf("%lld",&Rec[j].p[walk].x);
else scanf("%lld",&Rec[j].p[walk].y);
}
}
for(int i = 0 ; i < n ; ++ i)
{
vector<rec> v;
v.push_back(Rec[i]);
for(int j = i + 1 ; j < n ; ++ j)
{
int flag = 0;
for(int k = 0 ; k < v.size() ; ++ k)
{
if(v[k].isnotinme(Rec[j]))
{
flag = 1;
break;
}
}
if(!flag)
{
v.push_back(Rec[j]);
}
}
maxer = maxer > v.size() ? maxer : v.size();
v.clear();
v.push_back(Rec[i]);
for(int j = 0 ; j < n ; ++ j)
{
int flag = 0;
if(i != j)
{
for(int k = 0 ; k < v.size() ; ++ k)
{
if(v[k].isnotinme(Rec[j]))
{
flag = 1;
break;
}
}
if(!flag)
{
v.push_back(Rec[j]);
}
}
}
maxer = maxer > v.size() ? maxer : v.size();
}
cout << maxer << endl;
}

最后

以上就是动听白羊为你收集整理的矩形重叠（网易校招）的全部内容，希望文章能够帮你解决矩形重叠（网易校招）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。