牛客网-矩形重叠

package practice;

import java.util.Scanner;

public class RectangleOverlaps {
/**
 题目描述
	平面内有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
	*/
//	解题思路  取得所有可能的矩形情况 （x,y）-计算单个（x,y）在所有条件矩形里的重叠数量-获取所有（x,y）中的最大值
	public static void main(String args[]){
		Scanner input =new Scanner(System.in);
		int n;
		n=input.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]=input.nextInt();
        }
        for(int i=0;i<n;i++){
        	y1[i]=input.nextInt();
        }
        /*右上角*/
        for(int i=0;i<n;i++){
        	x2[i]=input.nextInt();
        }
        for(int i=0;i<n;i++){
        	y2[i]=input.nextInt();
        }
        int ans=0;
        int res=0;
      /* 列出所有的矩形框x,y的所有可能
       * 如果落在条件矩形i里则数量加一
       * ans为单个矩形i在所有条件矩形里的重叠数量
       * res为最大的落在条件按矩形里的数量
       * */
        for (int j = 0; j < n; j++) { //x值
            for (int k = 0; k < n; k++) { //y值
                for (int i = 0; i < n; i++) { //矩形
                    if (x1[j] >= x1[i] && x1[j] < x2[i] && y1[k] >= y1[i] && y1[k] < y2[i]) {
                        ans++;
                    }
                }
                res = res < ans ? ans : res;//比较每个 矩形i重叠的值 获取最大值
                ans = 0;
            }
        }
        System.out.println(res);
        
	}
}
牛客网-矩形重叠

推荐阅读
