蓝桥杯直线问题python

### 蓝桥杯竞赛中的直线问题 蓝桥杯竞赛中涉及的直线问题通常围绕几何学展开，尤其是判断点、线之间的关系以及计算某些特定条件下的最优解。以下是针对该类问题的一种通用解决方案。 #### 1. 判断三点共线 对于给定三个点 \(A(x_1, y_1)\), \(B(x_2, y_2)\), 和 \(C(x_3, y_3)\)，可以通过斜率来验证它们是否共线。如果 \((y_2 - y_1)/(x_2 - x_1) = (y_3 - y_2)/(x_3 - x_2)\)，则这三点共线[^4]。 实现此逻辑的 Python 示例代码如下： ```python def are_points_collinear(p1, p2, p3): # 计算向量 AB 和 AC 的叉积 cross_product = (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]) return cross_product == 0 # 测试用例 points = [(1, 1), (2, 2), (3, 3)] print(are_points_collinear(points[0], points[1], points[2])) # 输出 True 表示共线 ``` #### 2. 多条直线交点计数 当有多个矩形边长作为输入时，可以将其视为若干条平行于坐标轴的直线段。通过遍历每一对直线段并检测其是否有交点，可统计总交点数量[^5]。 下面是一个简单的算法框架用于处理此类情况： ```python from collections import defaultdict def count_intersections(rectangles): events = [] for rect in rectangles: ax, ay, bx, by = rect[:4] if ax != bx and ay != by: # 只考虑水平或垂直线段 continue if ax == bx: # 垂直线段 events.append(('V', min(ay, by), max(ay, by), ax)) elif ay == by: # 水平线段 events.append(('H', min(ax, bx), max(ax, bx), ay)) vertical_lines = defaultdict(list) horizontal_lines = [] for event_type, start, end, coord in events: if event_type == 'V': vertical_lines[(start, end)].append(coord) else: horizontal_lines.append((coord, start, end)) intersection_count = 0 for h_line in horizontal_lines: hy, hx_start, hx_end = h_line for v_range, vx_list in vertical_lines.items(): vy_start, vy_end = v_range if not (hy < vy_start or hy > vy_end): # 如果水平线穿过当前竖直线范围 for vx in vx_list: if hx_start <= vx <= hx_end: intersection_count += 1 return intersection_count rects_input = [[1, 1, 3, 3, 0, 0]] # 示例输入 print(count_intersections(rects_input)) # 输出交点总数 ``` 上述代码实现了基于事件驱动的方法来高效地查找所有相交点的数量。 --- #### 动态规划的应用场景扩展 尽管本题主要讨论的是几何问题，但在其他领域如子序列匹配等问题上也可以采用类似的分治策略或者动态转移方程进行优化求解[^6]。 --- ###