刷题笔记合集🔗

问题描述

小基是一名地理信息系统工程师，他需要处理大量的多段线数据。多段线是由一系列连续的点构成的，每个点都有 坐标。由于数据量太大，小基需要对这些多段线数据进行压缩，以减少存储空间和传输带宽。

压缩的原理是：如果三个连续的点在同一条直线上，那么中间的点就是冗余的，可以被删除。具体来说，对于连续的三个点 、 和 ，如果满足 ，则认为这三个点共线，可以删除中间点 。

请你帮助小基实现这个多段线压缩算法，计算压缩后剩余的点的数量。

输入格式

第一行包含一个整数 ，表示多段线中点的数量。

接下来 行，每行包含两个整数 和 ，表示第 个点的坐标。

输出格式

输出一个整数，表示压缩后剩余的点的数量。

样例输入1

5
1 1
2 2
3 3
4 4
5 5

样例输出1

2

样例输入2

7
1 1
2 2
3 3
4 3
5 2
6 1
7 0

样例输出2

3

样例输入3

6
1 1
2 2
3 3
4 5
5 4
6 6

样例输出3

6

样例解释

数据范围

题解

这道题目要求我们实现一个多段线压缩算法，核心思想是删除那些与相邻点共线的中间点。

首先，我们需要理解判断三点共线的数学原理。对于三个点 、 和 ，它们共线的条件是：

这个公式实际上是通过叉积来判断三点是否共线。如果叉积为0，则三点共线。

解题思路如下：

1. 如果点的数量小于3，则无法进行压缩，直接返回原始点的数量。
2. 创建一个新的点集，初始时包含第一个点（起点）。
3. 从第二个点开始遍历，对于每个点，判断它是否与前一个点和下一个点共线。
   • 如果共线，则跳过该点（即不将其添加到新的点集中）。
   • 如果不共线，则将该点添加到新的点集中。
4. 最后一个点（终点）始终保留。
5. 返回新点集的大小，即压缩后剩余的点的数量。

需要注意的是，我们需要连续地应用这个压缩过程，直到无法再压缩为止。这是因为删除一些点后，可能会出现新的三点共线的情况。

时间复杂度分析：

• 在最坏情况下，我们需要对每个点进行多次判断，时间复杂度为 。
• 但在实际应用中，由于大多数点不会被删除，时间复杂度通常接近 。

空间复杂度分析：

• 我们需要存储原始点集和压缩后的点集，空间复杂度为 。

对于给定的数据范围（），这个算法的效率是完全可以接受的。

参考代码

def is_collinear(p1, p2, p3):
    """判断三点是否共线"""
    # 计算叉积：(y3-y1)*(x2-x1) - (y2-y1)*(x3-x1)
    return (p3[1] - p1[1]) * (p2[0] - p1[0]) == (p2[1] - p1[1]) * (p3[0] - p1[0])

def compress_polyline():
    """压缩多段线"""
    # 读取点的数量
    n = int(input())
    
    # 如果点的数量小于3，无法压缩
    if n < 3:
        return n
    
    # 读取所有点的坐标
    points = []
    for _ in range(n):
        x, y = map(int, input().split())
        points.append((x, y))
    
    # 压缩多段线
    compressed = [points[0]]  # 起点始终保留
    
    i = 1
    while i < n - 1:
        # 如果当前点与前一个点和后一个点共线，则跳过该点
        if is_collinear(compressed[-1], points[i], points[i + 1]):
            i += 1
            continue
        
        # 否则，将当前点添加到压缩后的点集中
        compressed.append(points[i])
        i += 1
    
    # 终点始终保留
    if n > 1:
        compressed.append(points