首页 > 试题广场 >

裁减网格纸

[编程题]裁减网格纸

热度指数：21257 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

输出描述:

一行输出最小面积

示例1

输入

2
0 0
0 3

输出

算法知识视频讲解

Java

求个大厂offer

这题比较简单通过排序得到最高点和最低点从而获取长和宽，再选取最大的作为正方形的边长，唯一值得注意的是测试用例不止一组所以使用Scanner对象的hasNext()方法来获取多组用例

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            Vector<Integer> x = new Vector<Integer>();
            Vector<Integer> y = new Vector<Integer>();
            int n = sc.nextInt();
            for(int i = 0;i<n;i++)
            {
                x.add(sc.nextInt());
                y.add(sc.nextInt());
            }
            Collections.sort(x);
            Collections.sort(y);
            int height = y.get(n-1)-y.get(0);
            int width = x.get(n-1)-x.get(0);
            int max = Math.max(height,width);
            System.out.println(max*max);
        }
    }
}

发表于 2021-09-07 10:07:08 回复(0)

Java

蔚蓝丶

import java.util.*;

public class Main{
    public static void main (String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int[][] point= new int [n][2];
            for(int i=0;i<n;i++){
                point[i][0]=in.nextInt();
                point[i][1]=in.nextInt();
            }
            int minLeft = point[0][0];
            int maxLeft = point[0][0];
            int minRight = point[0][1];
            int maxRight = point[0][1];
            for(int i=0;i<n;i++){
                if (point[i][0]>maxLeft){
                    maxLeft=point[i][0]; 
                }
                if (point[i][0]<minLeft){
                    minLeft=point[i][0]; 
                }
                if (point[i][1]>maxRight){
                    maxRight=point[i][1]; 
                }
                if (point[i][1]<minRight){
                    minRight=point[i][1]; 
                }
            }
            int rect=Math.max(Math.abs(maxRight-minRight),Math.abs(maxLeft-minLeft));
            System.out.println(rect*rect);
        }
    }
}

发表于 2017-08-07 16:37:49 回复(0)

Java

fengyunzxd

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		int n = 0;
		
		while(scan.hasNext()){
			n = scan.nextInt();
			
			int x, y;
			
			int maxX = Integer.MIN_VALUE;
			int maxY = Integer.MIN_VALUE;
			int minX = Integer.MAX_VALUE;
			int minY = Integer.MAX_VALUE;
			
			while(n > 0){
				
				x = scan.nextInt();
				y = scan.nextInt();
				
				maxX = Math.max(maxX, x);
				maxY = Math.max(maxY, y);
				minX = Math.min(minX, x);
				minY = Math.min(minY, y);
				
				n--;
			}
			
            // 保证最小值为1，可以处理所有的点都是同一个点的情况。
			int a = (maxX - minX) > 0 ? (maxX - minX) : 1;
			int b = (maxY - minY) > 0 ? (maxY - minY) : 1;
			
			System.out.println((int)(Math.pow((Math.max(a, b)), 2)));
		}
	}
}

编辑于 2017-04-12 19:45:49 回复(1)

Java

zachaxy

public class CutGridPaper {  public static void main(String[] args) {  Scanner in = new Scanner(System.in);  int n = in.nextInt();  int left = 0;  int right = 0;  int top = 0;  int bottom = 0;   left = in.nextInt();  right = left;  top = in.nextInt();  bottom = top;   for (int i = 1; i < n; i++) {  int a = in.nextInt();  if (a < left) {  left = a;  } else if (a > right) {  right = a;  }   int b = in.nextInt();  if (b < top) {  top = b;  } else if (b > bottom) {  bottom = b;  }  }   long size = Math.max(right - left, bottom - top);   System.out.println(size * size);   } }

请问这段代码为何运行时说没有输出,但是按照所给的测试用例在本机上结果和测试所提供的结果是一样的啊

发表于 2017-04-07 15:43:21 回复(0)

Java

孙强Jimmy


	package com.jimmysun.baidu2016;

import java.util.Scanner;

public class GridPaper {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextInt()) {
			int n = 0;
			int minX, minY, maxX, maxY, xlength, ylength;
			int result;
			n = scanner.nextInt();
			Coordinate[] coordinates = new Coordinate[n];
			for (int i = 0; i < coordinates.length; i++) {
				coordinates[i] = new Coordinate();
				coordinates[i].setX(scanner.nextInt());
				coordinates[i].setY(scanner.nextInt());
			}
			minX = coordinates[0].getX();
			maxX = coordinates[0].getX();
			minY = coordinates[0].getY();
			maxY = coordinates[0].getY();
			for (int i = 1; i < coordinates.length; i++) {
				if (coordinates[i].getX() < minX) {
					minX = coordinates[i].getX();
				}
				if (coordinates[i].getX() > maxX) {
					maxX = coordinates[i].getX();
				}
				if (coordinates[i].getY() < minY) {
					minY = coordinates[i].getY();
				}
				if (coordinates[i].getY() > maxY) {
					maxY = coordinates[i].getY();
				}
			}
			xlength = maxX - minX;
			ylength = maxY - minY;
			if (xlength > ylength) {
				result = xlength * xlength;
			} else {
				result = ylength * ylength;
			}
			System.out.println(result);
		}
	}
}

class Coordinate {
	int x, y;

	public Coordinate() {
		x = 0;
		y = 0;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}
}

编辑于 2016-09-28 21:52:52 回复(0)

Java

金宝子

最小面积是最大坐标差的平方
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int 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();
            }
            Arrays.sort(x);
            Arrays.sort(y);
            int dit_x = x[x.length-1] - x[0];//最大x坐标差
            int dit_y = y[y.length-1] - y[0];//最大y坐标差
            if(dit_x > dit_y)//比较哪个坐标差大？
                System.out.println(dit_x * dit_x);
            else
                System.out.println(dit_y * dit_y);
        }
    }
}

发表于 2016-09-13 17:02:40 回复(0)

Java

詆調壹點

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int row = sc.nextInt();
			int[][] arr = new int[row][2];
			for (int i = 0; i < row; i ++ ) {
				for (int j = 0; j < 2; j ++ ) {
					arr[i][j] = sc.nextInt();
				}
			}
			int maxRow = 0, minRow = Integer.MAX_VALUE;
			int maxCol = 0, minCol = Integer.MAX_VALUE;
			for (int[] is:arr) {
				maxRow = maxRow < is[0] ? is[0] : maxRow;
				minRow = minRow > is[0] ? is[0] : minRow;
				maxCol = maxCol < is[1] ? is[1] : maxCol;
				minCol = minCol > is[1] ? is[1] : minCol;
			}
			int len = (maxCol - minCol) > (maxRow - minRow) ? (maxCol - minCol) : (maxRow - minRow);
			System.out.println(len * len);
		}
	}
}

发表于 2016-08-30 18:53:59 回复(0)

Java

Nestling

import java.util.Scanner;
public class Main {
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        
        int n = 0;
        while(in.hasNextInt()){
            n = in.nextInt();
            int minX = 0, maxX = 0, minY = 0, maxY = 0;
            minX = maxX = in.nextInt();
        	minY = maxY = in.nextInt();
            int x, y, t1,t2;
            for(int i = 1; i < n; i++){
                x = in.nextInt();
                y = in.nextInt();
                if(minX > x){
                	minX = x;
            	}
            	if(maxX < x){
                	maxX = x;
            	}
            	if(minY > y){
                	minY = y;
            	}
            	if(maxY < y){
                	maxY = y;
            	}
            }
            t1 = maxX - minX;
            t2 = maxY - minY;
            t1 = t1 > t2 ? t1 : t2;
            System.out.println(t1 * t1);
        }
    }    
}

运行出错，可能是内存占用问题。测试用例获取的数据不够，应该是内存占用太大的问题。

发表于 2016-08-10 16:14:22 回复(0)