华为OD机试真题---绘图机器（计算面积）

题目描述

绘图机器的绘图笔初始位置在原点(0,0)，机器启动后按照以下规则绘制直线：

1. 尝试沿着横线坐标正向绘制直线直到给定的终点E。
2. 期间可以通过指令在纵坐标轴方向进行偏移，offsetY为正数表示正向偏移，为负数表示负向偏移。

给定了横坐标终点值E以及若干条绘制指令，请计算绘制的直线和横坐标轴以及X=E的直线组成图形的面积。

输入描述

首行为两个整数N和E，表示有N条指令，机器运行的横坐标终点值E。

接下来N行，每行两个整数表示一条绘制指令X offsetY，用例保证横坐标X以递增排序的方式出现，且不会出现相同横坐标X。

取值范围：

• 0 < N <= 10000
• 0 <= X <= E <= 20000
• -10000 <= offsetY <= 10000

输出描述

一个整数，表示计算得到的面积，用例保证结果范围在0到4294967295之内。

解题思路

1. 初始化变量：包括总面积、上一个点的横坐标和纵坐标。
2. 遍历指令：对于每一条指令，计算当前段与X轴围成的面积，并累加到总面积中。
   • 面积 = (当前X - 上一个X) * |上一个Y|（因为上一个Y到当前Y之间是一个矩形或梯形的高，而宽度是当前X与上一个X的差）
   • 注意，这里使用了绝对值来计算高度，因为面积总是正的。
3. 处理最后一个段：如果最后一个点的X坐标小于E，则需要计算最后一个段与X=E的直线围成的面积。
4. 输出结果：输出计算得到的总面积。

Java实现示例

import java.util.Scanner;public class DrawingMachineArea {public static void main(String[] args) {try (Scanner scanner = new Scanner(System.in)) {// 读取N和Eint N = scanner.nextInt();int E = scanner.nextInt();// 输入验证if (N <= 0 || E <= 0) {throw new IllegalArgumentException("N 和 E 必须大于零");}// 初始化变量int lastX = 0; // 上一个点的横坐标int lastY = 0; // 上一个点的纵坐标long totalArea = 0; // 总面积，使用long类型以防止溢出// 读取指令并计算面积for (int i = 0; i < N; i++) {int currentX = scanner.nextInt();int offsetY = scanner.nextInt();// 输入验证if (currentX < 0 || currentX > E) {throw new IllegalArgumentException("currentX 必须在 [0, E] 范围内");}int currentY = lastY + offsetY; // 计算当前Y坐标// 计算当前段与X轴围成的面积int width = currentX - lastX;int height = Math.abs(currentY - lastY); // 使用绝对值计算高度// 溢出检测if (width > Integer.MAX_VALUE / height) {throw new ArithmeticException("计算面积时可能发生溢出");}long segmentArea = (long)width * height; // 使用long类型进行计算以防止溢出// 累加面积到总面积中totalArea += segmentArea;// 更新上一个点的坐标lastX = currentX;lastY = currentY;}// 计算最后一个段与X=E的直线围成的面积（如果有的话）if (lastX < E) {int width = E - lastX;long segmentArea = (long)width * Math.abs(lastY); // 使用long类型进行计算以防止溢出// 溢出检测if (totalArea > Long.MAX_VALUE - segmentArea) {throw new ArithmeticException("累加总面积时可能发生溢出");}totalArea += segmentArea;}// 输出结果System.out.println(totalArea);} catch (Exception e) {System.err.println("发生错误: " + e.getMessage());}
}}

注意事项

1. 输入处理：确保输入的格式正确，并按照题目描述的取值范围进行验证（虽然题目要求不需要显式验证，但在实际编程中应该考虑这一点）。
2. 面积计算：在计算面积时，使用长整型（long）来防止溢出。这是因为当N、E和offsetY的取值范围较大时，单个段的面积可能会超过int类型的最大值。
3. 最后一个段：不要忘记计算最后一个段与X=E的直线围成的面积（如果最后一个点的X坐标小于E）。
4. 输出格式：输出一个整数表示计算得到的面积，确保结果在题目给定的范围内内。
   为了提供一个运行示例，我将模拟一些输入数据，并展示如何使用上述Java代码来计算绘图机器绘制的直线与坐标轴围成的面积。由于我们不能直接在文本环境中运行代码，我将通过描述输入数据和预期输出来模拟这个过程。

输入数据示例

假设我们有以下输入数据：

4 10
2 3
4 -1
7 2
9 4

这表示：

• 有4条指令（N=4）。
• 横坐标终点值E=10。
• 指令依次为：
  1. 在X=2处，Y方向偏移+3（到达点(2,3)）。
  2. 在X=4处，Y方向偏移-1（到达点(4,2)）。
  3. 在X=7处，Y方向偏移+2（到达点(7,4)）。
  4. 在X=9处，Y方向偏移+4（到达点(9,8)）。

预期输出

我们需要计算由这些点和X=10的直线围成的面积。通过手动计算或运行代码，我们可以得到以下面积：

• 从(0,0)到(2,3)的面积：2 * 3 = 6
• 从(2,3)到(4,2)的面积：2 * 1 = 2（注意高度是|3-2|=1）
• 从(4,2)到(7,4)的面积：3 * 2 = 6
• 从(7,4)到(9,8)的面积：2 * 4 = 8
• 从(9,8)到(10,8)的面积（与X=10相交）：1 * 8 = 8

将这些面积相加，我们得到总面积：6 + 2 + 6 + 8 + 8 = 30。