首页 > 试题广场 >

矩形重叠

[编程题]矩形重叠
  • 热度指数：805 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

平面内有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
算法知识视频讲解
添加回答
南洋理工大学-LUWEI头像 南洋理工大学-LUWEI 
n = int(input())
x1 = [int(i) for i in input().split()]
y1 = [int(i) for i in input().split()]
x2 = [int(i) for i in input().split()]
y2 = [int(i) for i in input().split()]
 
result = 0;
for x in x1+x2:
    for y in y1+y2:
        count = 0
        for i in range(n):
            if x >= x1[i] and y >= y1[i] and x < x2[i] and y < y2[i]:
                count += 1
        result = max(result, count)
print(result)

发表于 2018-09-08 08:49:30 回复(1)
XH！头像 XH！

方法一

  1. 初始标记每个矩形区域重叠计数为1
  2. 遍历所有矩形，若两个矩形有重叠，则将重叠矩形加入集合，并记录重叠计数为两者之和
    不足：若50个矩形都重叠，newRec长度会达到千亿级别
    import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
private static int n;
private static int[][] rec; //0下标记录重叠计数
private static List newRec;
private static long res = 1;
public static void main(String[] args){
    int loop = 1;
    //System.setIn(No2.class.getResourceAsStream("2.txt"));
    Scanner scanner = new Scanner(System.in);
    //loop = scanner.nextInt();
    for (int i = 0; i < loop; ++i) {
        n = scanner.nextInt();
        rec = new int[n][5];
        newRec = new ArrayList();
        for (int j = 1; j <= 4; j++) {
            for (int k = 0; k < n; k++) {
                rec[k][j] = scanner.nextInt();
            }
        }
        for (int k = 0; k < n; k++) {
            rec[k][0] = 1;
        }
        solve();
        output();
    }
    scanner.close();
}
private static void solve() {
    for (int i = 1; i < n; i++) {
        int[] cover;
        for (int j = 0, len = newRec.size(); j < len; ++j) {
            if((cover = getCover(newRec.get(j), rec[i])) != null) {
                newRec.add(cover);
            }
        }
        for (int j = 0; j < i; j++) {
            if((cover = getCover(rec[j], rec[i])) != null) 
                newRec.add(cover);
        }
    }
}
private static int[] getCover(int[] a, int[] b) {
    int x1 = Math.max(a[1], b[1]);
    int y1 = Math.max(a[2], b[2]);
    int x2 = Math.min(a[3], b[3]);
    int y2 = Math.min(a[4], b[4]);
    if(x1 < x2 && y1 < y2) {
        res = Math.max(res, a[0] + b[0]);
        return new int[]{a[0] + b[0], x1, y1, x2, y2};
    }
    return null;
}
private static void output() {
    System.out.println(res);
}
}

方法二
点计数法，重叠后的矩形左下角坐标一定是{x1[0]~x1[50], y1[0]~y1[50]}这2500个点中产生，只要分别判断这些点在多少矩形中即可

import java.util.Scanner;
public class Main {
    private static int n;
    private static int[][] rec;
    private static long res = 1;
    public static void main(String[] args){
        int loop = 1;
        //System.setIn(No2.class.getResourceAsStream("2.txt"));
        Scanner scanner = new Scanner(System.in);
        //loop = scanner.nextInt();
        for (int i = 0; i < loop; ++i) {
            n = scanner.nextInt();
            rec = new int[n][4];
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < n; k++) {
                    rec[k][j] = scanner.nextInt();
                }
            }
            solve();
            output();
        }
        scanner.close();
    }
    private static void solve() {
        int x, y, count;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                x = Math.max(rec[i][0], rec[j][0]);
                y = Math.max(rec[i][1], rec[j][1]);
                count = 0;
                for (int k = 0; k < n; k++) {
                    if(x >= rec[k][0] && y >= rec[k][1] && x < rec[k][2] && y < rec[k][3])
                        ++count;
                }
                res = Math.max(count, res);
            }
        }
    }
    private static void output() {
        System.out.println(res);
    }
}
编辑于 2018-07-05 00:06:28 回复(12)
VMatrix头像 VMatrix
曾经做过一维的区间重叠问题，用的是线段树。不过这题拓展到二维了，有时间想一想解决方案。
发表于 2018-07-06 18:16:04 回复(1)
递归怪头像 递归怪 
左程云的思路：最大重叠区域的底边一定是某个矩形的底边。
方法：
1 按下边界对矩形升序排序
2 遍历每个矩形，构造这样一个集合：集合中其他矩形的下边界小于等于该矩形的下边界，
  集合中其他矩形的上边界大于该矩形的下边界
3 对每个集合调用最大线段重叠问题算法原型


import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
       
        int n = scanner.nextInt();
        int[] x1 = new int[n];
        int[] y1 = new int[n];
        int[] x2 = new int[n];
        int[] y2 = new int[n];
        for (int i = 0; i < n; i++) {
            x1[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            y1[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            x2[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            y2[i] = scanner.nextInt();
        }
        Node[] nodes = new Node[x1.length];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new Node(x1[i], y1[i], x2[i], y2[i]);
        }
        System.out.println(maxRectangleCover(nodes));
    }

    public static class Node {
        public int x1;
        public int y1;
        public int x2;
        public int y2;

        public Node(int x1, int y1, int x2, int y2) {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }
    }

    public static int maxRectangleCover(Node[] nodes) {
        Arrays.sort(nodes, (a, b) -> a.y1 - b.y1);
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.y2 - b.y2);
        int maxCover = 0;
        for (int i = 0; i < nodes.length; i++) {
            while (!pq.isEmpty() && pq.peek().y2 <= nodes[i].y1) {
                pq.poll();
            }
            pq.add(nodes[i]);
            Node[] subNodes = pq.toArray(pq.toArray(new Node[0]));
            maxCover = Math.max(maxCover, maxLineCover(subNodes));
        }
        return maxCover;
    }

    public static int maxLineCover(Node[] nodes) {
        Arrays.sort(nodes, (a, b) -> a.x1 - b.x1);
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.x2 - b.x2);
        int maxCover = 0;
        for (int i = 0; i < nodes.length; i++) {
            while (!pq.isEmpty() && pq.peek().x2 <= nodes[i].x1) {
                pq.poll();
            }
            pq.add(nodes[i]);
            maxCover = Math.max(maxCover, pq.size());
        }
        return maxCover;
    }
}

发表于 2022-09-11 22:39:47 回复(0)
C/C++
哈斯基小胖毛头像 哈斯基小胖毛 
#include <bits/stdc++.h>
using namespace std;
struct node {
	int point[4];  //x1,y1,x2,y2
} rec[55];
vector<int> xx;
vector<int> yy;
int maxn = 0;
int main() {
	int n; cin >> n;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < n; j++) {
			cin >> rec[j].point[i];
			if (i % 2 == 0) xx.push_back(rec[j].point[i]);
			else yy.push_back(rec[j].point[i]);
		}
	}
	int sz = xx.size();
	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < sz; j++) {
			int cnt = 0;
			for (int t = 0; t < n; t++) {  //走所有矩形
				int x1 = rec[t].point[0];
				int x2 = rec[t].point[2];
				int y1 = rec[t].point[1];
				int y2 = rec[t].point[3];
				//不取等号防止重复，控制边界
				if (xx[i] < x2 && xx[i] >= x1 && yy[j] < y2 && yy[j] >= y1) cnt++;
			}
			maxn = maxn > cnt ? maxn : cnt;
		}
	}
	cout << maxn;
	return 0;
}

编辑于 2021-12-16 13:59:36 回复(0)
牛客209181号头像 牛客209181号
上边好多人的回答都属于没有考虑边界条件。
关于举行重叠的方式一共有四种。
分为单纯边重叠，单纯角重叠，包含重叠，交叉重叠。
好多人的想法是判断A矩形的端点在不在B内，这种方法只能检测出单纯边重叠，单纯角重叠，包含重叠。
有人可能单纯的认为因为A与B重叠，所以B与A重叠。于是算出来的结果直接除2。如果按照上述这种方法，对于A与B不同的重叠方式，检测到的重叠数是不同的，并不能简单的除2。
单纯边重叠 1
单纯角重叠 2
包含重叠 1
交叉重叠 0
由上得知这个算法存在严重问题。
反过来思考即可，A与B不重叠的方法很简单，xa1>=xb2 || xa2<=xb1 || ya1<=yb2 || ya2>=yb1
由于一共只有50个矩形，最坏情况下，总共有100个x和y的取值。
写二重循环，判断A与list里其后方的其他矩形是否不重叠，然后取差即为重叠，共循环（49+1）/ 2 * 49 =2450即可。
由于判断时，A与list里其后方的其他矩形比较。最后结果无需除2。
发表于 2019-11-14 09:23:57 回复(0)
万叶飞花头像 万叶飞花 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][4];
        List<Integer> xList = new ArrayList<>();
        List<Integer> yList = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < n; j++) {
                arr[j][i] = sc.nextInt();
                if (i == 0 || i == 2) {
                    xList.add(arr[j][i]);
                }
                if (i == 1 || i == 3) {
                    yList.add(arr[j][i]);
                }
            }
        }
        int ret = 0;
        for (int x : xList) {
            for (int y : yList) {
                int cnt = 0;
                for (int i = 0; i < n; i++) {
                    if (x >= arr[i][0] && x < arr[i][2] && y >= arr[i][1] && y < arr[i][3]) {
                        cnt++;
                    }
                }
                if (cnt > ret) {
                    ret = cnt;
                }
            }
        }
        System.out.println(ret);
    }
}
发表于 2019-08-03 00:18:36 回复(0)
望阳赏月头像 望阳赏月
通过40%，可能少考虑了某些特殊情况，有大佬看出来的可以留个言，谢谢啦！！！
通过只判断不重叠的矩形条件，来计算每个矩形的重叠个数。
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] x1 = new long[n];
        long[] y1 = new long[n];
        long[] x2 = new long[n];
        long[] y2 = new long[n];
        int  max = 0;
        for(int i = 0; i < n; i++){
            x1[i] = in.nextLong();
        }
        for(int i = 0; i < n; i++){
            y1[i] = in.nextLong();
        }
        for(int i = 0; i < n; i++){
            x2[i] = in.nextLong();
        }
        for(int i = 0; i < n; i++){
            y2[i] = in.nextLong();
        }
        for(int i=0; i < n; i++){
            int temp = 0;
            for(int j = 0; j < n; j++){
                 //当前矩形的左下角坐标是否在对比矩形的右上角坐标的上方或右侧
                if(x1[j] >= x2[i] || y1[j] >= y2[i]){
                    continue;
                }else if(x2[j] <= x1[i] || y2[j] <= y1[i]){
                 //当前矩形的右上角坐标是否在对比矩形的左下角坐标的下方或左侧
                    continue;
                }else{
                     temp++;
               }
            }
            if(temp > max){
                max = temp;
            }
        }
        System.out.println(max);
        in.close();
    }
}

发表于 2018-08-20 16:26:07 回复(0)
时钟时代头像 时钟时代
我的通过百分40，举的反例n=50且全是-328069945这种的，我的核心思想是先看那种情况会出现同轴坐标发生交叉或同位置的重叠(如两个矩形的左横坐标相等)，该方法用judge1描述，然后如果两个矩形的x y的四个坐标都分别满足judge1，那么就判断这两个矩形有重叠，这个方法用judge描述。其余的思路和Icarus4Yu一样。不知道哪里出了问题。
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] array = new long[n][5]; 
        for(int j=1;j<=4;j++){
            for(int i=0;i<n;i++){
                array[i][j] = sc.nextInt();
            }
        }
        
        for(int i=0;i<n;i++){
            array[i][0]=1;
        }
        
        long max = 1;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(judge(array[i][1],array[i][2],array[i][3],array[i][4],array[j][1],array[j][2],array[j][3],array[j][4])){
                    array[i][0]+=1;
                    array[j][0]+=1;
                    max = Math.max(max,Math.max(array[i][0],array[j][0]));
                }
            }
        }
        
        System.out.println(max);
    }
    
    public static boolean judge(long x1,long y1, long x2,long y2, long x11,long y11,long x22,long y22){
        if(judge1(x1,x2,x11,x22)&&judge1(y1,y2,y11,y22)){
            return true;
        }
        return false;
    }
    
    public static boolean judge1(long a, long b, long c, long d){
        if((c>a&&c<b)||(d>a&&d<b)){
            return true;
        }else if((a>c&&a<d)||(b>c&&b<d)){
            return true;
        }else if((a==c)||(b==d)){
            return true;
        }
        return false;
    }
}
发表于 2018-08-18 23:21:19 回复(0)
fly_24头像 fly_24
//只过了50%，判断每个矩形的四个顶点在其他多少个矩形中，取最大值。
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        int[] x1,y1,x2,y2;
        x1 = new int[n];
        y1 = new int[n];
        x2 = new int[n];
        y2 = new int[n];
        int minx1 = Integer.MAX_VALUE;
        int miny1 = Integer.MAX_VALUE;
        int maxx2 = Integer.MIN_VALUE;
        int maxy2 = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            x1[i] = sc.nextInt();
            if(x1[i]<minx1){
                minx1 = x1[i];
            }
        }
        for(int i=0;i<n;i++){
            y1[i] = sc.nextInt();
            if(y1[i]<miny1){
                miny1 = y1[i];
            }
        }
        for(int i=0;i<n;i++){
            x2[i] = sc.nextInt();
            if(x2[i]>maxx2){
                maxx2 = x2[i];
            }
        }
        for(int i=0;i<n;i++){
            y2[i] = sc.nextInt();
            if(y2[i]>maxy2){
                maxy2 = y2[i];
            }
        }
        //
        int max = 0;
        for(int i = 0;i<n;i++){   //n个矩形
            int count = 0;
            for(int j=0;j<n;j++){  
                if(j!=i){         //顶点在其他n-1个矩形中
                    if(x1[i]>x1[j]&&x1[i]<x2[j]&&y1[i]>y1[j]&&y1[i]<y2[j]){     //左下角顶点
                        count++;
                    }
                }
            }
            if(count>max){
                max = count;
            }
             
            count = 0;
            for(int j=0;j<n;j++){  
                if(j!=i){         //顶点在其他n-1个矩形中
                    if(x1[i]>x1[j]&&x1[i]<x2[j]&&y2[i]>y1[j]&&y2[i]<y2[j]){     //左上角顶点
                        count++;
                    }
                }
            }
            if(count>max){
                max = count;
            }
             
            count = 0;
            for(int j=0;j<n;j++){  
                if(j!=i){         //顶点在其他n-1个矩形中
                    if(x2[i]>x1[j]&&x2[i]<x2[j]&&y1[i]>y1[j]&&y1[i]<y2[j]){     //右下角顶点
                        count++;
                    }
                }
            }
            if(count>max){
                max = count;
            }
             
            count = 0;
            for(int j=0;j<n;j++){  
                if(j!=i){         //顶点在其他n-1个矩形中
                    if(x2[i]>x2[j]&&x1[i]<x2[j]&&y2[i]>y1[j]&&y2[i]<y2[j]){     //右上角顶点
                        count++;
                    }
                }
            }
            if(count>max){
                max = count;
            }
             
        }
 
        //判断完全重合的情况
        for(int i=0;i<n;i++){
            int count1 = 0;
            for(int j=0;j<n;j++){
                if(j!=i){
                    if(x1[i]==x1[j]&&y1[i]==y1[j]&&x2[i]==x2[j]&&y2[i]==y2[j]){
                        count1++;
                    }
                }
            }
            if(count1>max){
                max = count1;
            }
             
        } 
        System.out.println(max+1);
    }
}
发表于 2018-08-10 20:56:55 回复(0)
提交观点

问题信息

穷举 网易 2018 高级结构 数学 Java工程师
上传者：小小
难度：
10条回答 4711浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号