2018网易计算机视觉笔试实习生编程题

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

【题目分析】：题目为判断矩形的重叠个数，通过枚举的方式，可以得到结果复杂度为O(n^3)，只要有一个点是包含关系即可。矩形一个点再另一个矩形内就可以满足重叠。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 55;
int a1[maxn] , b1[maxn] ;
int a2[maxn] , b2[maxn] ;
set<int> xx, yy;
int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d", &a1[i]);
xx.insert(a1[i]);
}
for (int i = 0; i < n; i++){
scanf("%d", &b1[i]);
yy.insert(b1[i]);
}
for (int i = 0; i < n; i++){
scanf("%d", &a2[i]);
xx.insert(a2[i]);
}
for (int i = 0; i<n; i++){
scanf("%d", &b2[i]);
yy.insert(b2[i]);
}
int ans = 0;
for (int x : xx){
for (int y : yy){
int cnt = 0;
for (int i = 0; i<n; i++){
if (a1[i] <= x && b1[i] <= y && a2[i]>x &&b2[i]>y)cnt++;
}
ans = max(ans, cnt);
}
}
printf("%dn", ans);
return 0;
}

最后

以上就是安静蜡烛为你收集整理的2018网易计算机视觉笔试实习生编程题的全部内容，希望文章能够帮你解决2018网易计算机视觉笔试实习生编程题所遇到的程序开发问题。

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