首页 > ACM题库 > 九度OJ > 九度-1020-最小长方形[解题代码]
2013
12-12

九度-1020-最小长方形[解题代码]

题目来源:2007年浙江大学计算机及软件工程研究生机试真题

题目描述:
    给定一系列2维平面点的坐标(x, y),其中x和y均为整数,要求用一个最小的长方形框将所有点框在内。长方形框的边分别平行于x和y坐标轴,点落在边上也算是被框在内。
输入:

    测试输入包含若干测试用例,每个测试用例由一系列坐标组成,每对坐标占一行,其中|x|和|y|小于 231;一对0 坐标标志着一个测试用例的结束。注意(0, 0)不作为任何一个测试用例里面的点。一个没有点的测试用例标志着整个输入的结束。

输出:

    对每个测试用例,在1行内输出2对整数,其间用一个空格隔开。第1对整数是长方形框左下角的坐标,第2对整数是长方形框右上角的坐标。

样例输入:
12 56
23 56
13 10
0 0
12 34
0 0
0 0
样例输出:
12 10 23 56
12 34 12 34

java 代码如下:
import java.util.Scanner;

public class Main {

	static int minx,miny,maxx,maxy;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		while(scan.hasNextInt()){
			minx = 1000;
			miny = 1000;
			maxx = -1000;
			maxy = -1000;
			int a = scan.nextInt();
			int b = scan.nextInt();
			if(a==0 && b==0)
				break;
			while(true){
				
				if(a==0 && b==0)
					break;
				if(minx > a)
					minx = a;
				if(maxx < a)
					maxx = a;
				if(miny > b)
					miny = b;
				if(maxy < b)
					maxy = b;
				a = scan.nextInt();
				 b = scan.nextInt();
			}
			System.out.println(minx+" "+miny+" " + maxx +" " + maxy);
		}
	}
}
/**************************************************************
	Problem: 1020
	User: coder
	Language: Java
	Result: Accepted
	Time:150 ms
	Memory:19096 kb
****************************************************************/


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。