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", area);

    return 0;
}

• Javascript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let N, E;
let area = 0;
let last_x = 0, last_y = 0;
let lineCount = 0;

rl.on('line', (line) => {
    if (lineCount === 0) {
        [N, E] = line.split(' ').map(Number);
    } else {
        const [x, offset_y] = line.split(' ').map(Number);
        
        // 计算当前梯形的面积并加到总面积中
        area += (x - last_x) * Math.abs(last_y);
        
        // 更新上一个点的坐标
        last_x = x;
        last_y += offset_y;

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

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int E = scanner.nextInt();

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

        for (int i = 0; i < N; i++) {
            int x = scanner.nextInt();
            int offsetY = scanner.nextInt();
            
            // 计算当前梯形的面积并加到总面积中
            area += (long)(x - lastX) * Math.abs(lastY);
            
            // 更新上一个点的坐标
            lastX = x;
            lastY += offsetY;
        }

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

        System.out.println(area);
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int N, E;
    cin >> 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;
        cin >> x >> offset_y;
        
        // 计算当前梯形的面积并加到总面积中
        area += static_cast<long long>(x - last_x) * abs(last_y);
        
        // 更新上一个点的坐标
        last_x = x;
        last_y += offset_y;
    }

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

    cout << area << endl;

    return 0;
}