E卷-(100分)绘图机器
绘图机器
问题描述
有一台绘图机器,其绘图笔的初始位置在原点 。机器启动后按照以下规则绘制直线:
- 沿着横坐标正向绘制直线,直到给定的终点 。
- 在绘制过程中,可以通过指令在纵坐标方向进行偏移。 为正数表示向上偏移,为负数表示向下偏移。
给定横坐标终点值 以及若干条绘制指令,请计算绘制的直线与横坐标轴以及 的直线所围成的图形面积。
输入格式
第一行包含两个整数 和 ,表示有 条指令,机器运行的横坐标终点值为 。
接下来 行,每行两个整数表示一条绘制指令 。
保证横坐标 以递增排序的方式出现,且不会出现相同横坐标 。
输出格式
输出一个整数,表示计算得到的面积。
样例输入
4 10
1 1
2 1
3 1
4 -2
样例输出
12
样例输入
2 4
0 1
2 -2
样例输出
4
数据范围
题解
这道题的核心思想是利用梯形面积公式来计算总面积。
以下是解题思路:
-
初始化面积 为 0,上一个点的坐标 为 。
-
遍历每条指令:
- 计算当前指令与上一个点之间形成的梯形面积,并加到总面积中。
- 更新 为当前指令的坐标。
-
最后,如果终点 大于最后一个指令的 坐标,还需要计算最后一段的矩形面积。
关键点在于梯形面积的计算:面积 = (当前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;
}
#OD#OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记