最新华为OD机试真题-多段线路径压缩(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 多段线路径压缩(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🎚 多段线路径压缩

题目描述

LYA 是一名出色的程序员,她正在开发一款图像处理软件。在处理图像时,需要存储图像中的多段线路径。为了节省存储空间,LYA 想要对路径进行压缩。

路径由若干个像素点组成,每个像素点用其行号和列号表示。为简化处理,多段线的走向只能是水平、竖直或 度斜向。例如,一条路径可以表示为:

但是,这种表示方法存在冗余。实际上,我们只需存储路径的关键点(起点、拐点和终点),就可以完整地表示整条路径。在上面的例子中,只需存储以下 个点即可:

现在,给定一条包含若干冗余点的路径,请你将其压缩为最简形式。

输入格式

输入一行,包含偶数个整数,表示原始路径。每两个整数表示一个像素点的行号和列号,整数之间用空格隔开。

输出格式

输出一行,包含偶数个整数,表示压缩后的路径。每两个整数表示一个像素点的行号和列号,整数之间用空格隔开。

样例输入

2 8 3 7 3 6 3 5 4 4 5 3 6 2 7 3 8 4 7 5

样例输出

2 8 3 7 3 5 6 2 8 4 7 5

数据范围

• 行号和列号的范围为 。
• 输入数据至少包含两个像素点。

题解

我们可以遍历原始路径中的所有像素点,依次判断每个点是否为关键点。判断方法如下:

1. 如果当前点是路径的起点,则它一定是关键点。
2. 如果当前点与前一个关键点在同一条直线上,则它不是关键点,否则它是关键点。

为了判断三个点是否在同一条直线上,我们可以分别计算前两个点的斜率和后两个点的斜率,如果两个斜率相等,则这三个点在同一条直线上。注意,由于坐标都是整数,为避免除法带来的精度问题,我们可以通过计算两个向量的叉积是否为零来判断斜率是否相等。

参考代码

• Python

def gcd(a, b):
    if a == 0 or b == 0:
        return 1
    while b:
        a, b = b, a % b
    return a

points = list(map(int, input().split()))
compressed = []

for i in range(0, len(points) - 2, 2):
    x1, y1 = points[i], points[i + 1] 
    x2, y2 = points[i + 2], points[i + 3]
    if not compressed:
        compressed.append(x1)
        compressed.append(y1)
    else:
        x0, y0 = compressed[-2], compressed[-1]
        dx1, dy1 = x1 - x0, y1 - y0
        dx2, dy2 = x2 - x1, y2 - y1
        g1, g2 = gcd(dx1, dy1), gcd(dx2, dy2)
        if dx1 // g1 != dx2 // g2 or dy1 // g1 != dy2 // g2:
            compressed.append(x1)
            compressed.append(y1)

compressed.extend(points[-2:])
print(*compressed)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        int n = input.length;
        int[] points = new int[n];
        f