裁减网格纸（贪心）

本文主要是介绍裁减网格纸（贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
度度熊有一张网格纸，但是纸上有一些点过的点，每个点都在网格点上，若把网格看成一个坐标轴平行于网格线的坐标系的话，每个点可以用一对整数x，y来表示。度度熊必须沿着网格线画一个正方形，使所有点在正方形的内部或者边界。然后把这个正方形剪下来。问剪掉正方形的最小面积是多少。
输入描述:
第一行一个数n(2≤n≤1000)表示点数，接下来每行一对整数xi,yi(－1e9<=xi,yi<=1e9)表示网格上的点

输出描述:
一行输出最小面积

输入例子:
2
0 0
0 3

输出例子:
9

解题思路
一开始还一直在网格布线里绕，后来想想不对劲啊，没那么复杂啊o(╯□╰)o，其实很简单的啊。。
因为要把所有的点都减在一个正方形的格子里，所以只要判断所有点的横坐标和纵坐标的最小值和最大值。
比较下横坐标和纵坐标各自最大值和最小值的差，选择差最大的作为正方形的边长即可求得最小的正方形。

public static void main(String[] args) {// TODO Auto-generated method stubScanner scan = new Scanner(System.in);while(scan.hasNextLine()){int n = Integer.parseInt(scan.nextLine());int p[][] = new int[n][2];int i = 0;while(i < n){String str[] = scan.nextLine().split("\\s");p[i][0] = Integer.parseInt(str[0]);p[i][1] = Integer.parseInt(str[1]);i++;}System.out.println(getNumOfSquare(p,n));}}public static int getNumOfSquare(int plot[][],int n){int sum = 0;int i,j;int xMin=Integer.MAX_VALUE,yMin = Integer.MAX_VALUE;int xMax = Integer.MIN_VALUE, yMax = Integer.MIN_VALUE;for(i = 0 ; i < n; i++){if (plot[i][0] < xMin) {xMin = plot[i][0];}if(plot[i][0] > xMax){xMax = plot[i][0];}if (plot[i][1] < yMin) {yMin = plot[i][1];}if(plot[i][1] > yMax){yMax = plot[i][1];}       }       int tmp = (yMax - yMin) > (xMax - xMin) ? yMax - yMin : xMax - xMin;return sum = tmp * tmp;}

小结：看清楚题目，再作答。

这篇关于裁减网格纸（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---