浙江大学07计算机上机题：最小长方形区域求解算法

该文档是浙江大学07年计算机上机考试的一道题目及其解法，主要涉及的是算法设计中的几何问题——寻找最小包围矩形。题目要求在给定一系列二维平面点的坐标（x, y）的情况下，找到一个最小的长方形，使得这些点都被框在矩形内部或边界上，矩形的边与x和y坐标轴平行。 首先，题目描述了输入格式，测试用例由一系列坐标组成，每对坐标占一行，其中x和y都是整数，且绝对值小于2^31。输入以一对0坐标作为测试用例的结束标志，而(0, 0)不会出现在测试用例内，且当没有任何点时，表示输入结束。 输出部分需要对于每个测试用例，输出矩形的左下角坐标和右上角坐标，用空格分隔。样例输入和输出给出了具体的例子，如输入的点集合（1256, 2356, 1310, 1234），其最小包围矩形为左下角(12, 10)和右上角(23, 56)。 提供的C++代码分为两部分。第一段代码使用一个while循环，通过不断更新x1、y1（左下角坐标）和x2、y2（右上角坐标）来找到最小包围矩形。每次读取一对坐标后，如果这个坐标比当前的x1或y1小，则更新相应的边界；如果比x2或y2大，则更新相应的边界。 第二段代码定义了两个辅助函数Max()和Min()，用于找到数组中的最大值和最小值。它们分别用于处理x坐标和y坐标的范围。在主函数中，通过输入的m和n获取当前测试用例的x坐标和y坐标，并存储在数组a1和a2中，然后调用这两个函数找到每个维度的最大值和最小值，进而确定矩形的边界。 这道题目考察了学生对数据结构（数组）和基本算法（查找最大值/最小值）的理解，以及如何应用到实际问题中，求解空间中的几何形状。通过解答此题，学生可以提升编程能力，理解如何利用循环和条件语句进行迭代操作，以及如何优化空间复杂度，以求得最优解。