E卷-(100分)绘图机器

绘图机器

问题描述

有一台绘图机器，其绘图笔的初始位置在原点 。机器启动后按照以下规则绘制直线：

1. 沿着横坐标正向绘制直线，直到给定的终点 。
2. 在绘制过程中，可以通过指令在纵坐标方向进行偏移。 为正数表示向上偏移，为负数表示向下偏移。

给定横坐标终点值 以及若干条绘制指令，请计算绘制的直线与横坐标轴以及 的直线所围成的图形面积。

输入格式

第一行包含两个整数 和 ，表示有 条指令，机器运行的横坐标终点值为 。

接下来 行，每行两个整数表示一条绘制指令 。

保证横坐标 以递增排序的方式出现，且不会出现相同横坐标 。

输出格式

输出一个整数，表示计算得到的面积。

样例输入

4 10
1 1
2 1
3 1
4 -2

样例输出

12

样例输入

2 4
0 1
2 -2

样例输出

4

数据范围

题解

这道题的核心思想是利用梯形面积公式来计算总面积。

以下是解题思路：

1. 初始化面积 为 0，上一个点的坐标 为 。

2. 遍历每条指令：

   • 计算当前指令与上一个点之间形成的梯形面积，并加到总面积中。
   • 更新 为当前指令的坐标。

3. 最后，如果终点 大于最后一个指令的 坐标，还需要计算最后一段的矩形面积。

关键点在于梯形面积的计算：面积 = (当前x - 上一个x) * |上一个y|。使用绝对值是因为 可能为负，但面积始终为正。

时间复杂度为 ，其中 是指令的数量。这个复杂度对于给定的数据范围（）是完全可以接受的。

参考代码

• Python

# 读取输入
N, E = map(int, input().split())

area = 0  # 初始化面积
last_x, last_y = 0, 0  # 初始化上一个点的坐标

# 遍历每条指令
for _ in range(N):
    x, offset_y = map(int, input().split())
    # 计算当前梯形的面积并加到总面积中
    area += (x - last_x) * abs(last_y)
    # 更新上一个点的坐标
    last_x, last_y = x, last_y + offset_y

# 如果终点E大于最后一个指令的x坐标，计算最后一段的面积
if E > last_x:
    area += (E - last_x) * abs(last_y)

# 输出结果
print(area)

• C

#include <stdio.h>
#include <stdlib.h>

int main() {
    int N, E;
    scanf("%d %d", &N, &E);

    long long area = 0;  // 使用long long避免整数溢出
    int last_x = 0, last_y = 0;

    for (int i = 0; i < N; i++) {
        int x, offset_y;
        scanf("%d %d", &x, &offset_y);
        
        // 计算当前梯形的面积并加到总面积中
        area += (long long)(x - last_x) * abs(last_y);
        
        // 更新上一个点的坐标
        last_x = x;
        last_y += offset_y;
    }

    // 如果终点E大于最后一个指令的x坐标，计算最后一段的面积
    if (E > last_x) {
        area += (long long)(E - last_x) * abs(last_y);
    }

    printf("%lld\n", ar