裁减网格纸找x轴与y轴最大的坐标差

你的名字 2022-09-26 02:57 120阅读 0赞

裁减网格纸

*  热度指数：1908时间限制：1秒空间限制：32768K
 *  本题知识点： [贪心][Link 1]
 *  [ 算法知识视频讲解][Link 2]

## 题目描述 ##

度度熊有一张网格纸，但是纸上有一些点过的点，每个点都在网格点上，若把网格看成一个坐标轴平行于网格线的坐标系的话，每个点可以用一对整数x，y来表示。度度熊必须沿着网格线画一个正方形，使所有点在正方形的内部或者边界。然后把这个正方形剪下来。问剪掉正方形的最小面积是多少。

##### 输入描述: #####

第一行一个数n(2≤n≤1000)表示点数，接下来每行一对整数xi,yi(－1e9<=xi,yi<=1e9)表示网格上的点

##### 输出描述: #####

一行输出最小面积

##### 输入例子: #####

2
    0 0
    0 3

##### 输出例子: #####

注意：题目中要求 正方形 是按照网格线剪得，所以是要求x轴 或 y 轴方向 的 坐标的最大差值，然后平方为面积。如果没有这个要求，应该是找距离最远的两个点。

/**
    注意：题目中要求 正方形 是按照网格线剪得，所以是要求x轴 或 y 轴方向 的 坐标的最大差值，
    然后平方为面积。如果没有这个要求，应该是找距离最远的两个点。
    */
    
    import java.util.*;
    public class Main{
        public static void main(String[] args){
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                int n;
            	n=in.nextInt();
            	int[] x = new int[n];
            	int[] y = new int[n];
            	for(int i=0;i<n;i++){
                	x[i]=in.nextInt();
                	y[i]=in.nextInt();
           	 	}
            	int maxX=Integer.MIN_VALUE;
            	int maxY=Integer.MIN_VALUE;
            	int minX=Integer.MAX_VALUE;
            	int minY=Integer.MAX_VALUE;
            	for(int i=0;i<n;i++){
                	maxX=Math.max(maxX,x[i]);
                	maxY=Math.max(maxY,y[i]);
                	minX=Math.min(minX,x[i]);
                	minY=Math.min(minY,y[i]);
            	}
            	int side=Math.max((maxX-minX),(maxY-minY));
            	System.out.println(side*side);
            }
            
        }
    }

[Link 1]: http://www.nowcoder.com/questionCenter?questionTypes=000100&mutiTagIds=592
[Link 2]: http://www.nowcoder.com/courses/1