2019校招真题编程练习 - 6 - 矩形重叠

题目描述

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

思路

矩形重叠：

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

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] rect = new int[n][4];
        for(int i=0; i<4; i++){
            for(int j=0; j<n; j++){
                rect[j][i] = in.nextInt();
            }
        }
        int sum = 1;//重叠数目
        
        for(int i=0; i<n; i++){
            for(int j=i+1;j<n; j++){
                int x = Math.max(rect[j][0],rect[i][0]);
                int y = Math.max(rect[j][1],rect[i][1]);
                int count = 0;
                for(int k=0; k<n; k++){
                    if(x>=rect[k][0] && y>=rect[k][1] && x<rect[k][2] && y<rect[k][3]){
                        ++count;
                    }
                }
                sum = Math.max(count,sum);
            }
        }
        
        
            
        System.out.println(sum);
    }
}