📝 学习笔记：计算多条线段覆盖的整数点数量

1. 问题描述

在二维平面上给定 n 条线段（起点 (ux, uy) 到 终点 (vx, vy)），求有多少个整数坐标点被至少两条不同的线段覆盖。

2. 核心算法思路

此题的本质是离散化遍历线段上的所有整数点。

• 利用 GCD 计算步长：线段上两个相邻整数点的距离（步长）可以通过 dx 和 dy 的最大公约数求得。

• 哈希映射 (Hash Map)：将二维坐标映射为一维整数，用于统计每个点的出现次数。

• 增量统计：仅在点的覆盖次数从 1 变为 2 时增加计数，避免重复统计。

3. 关键代码逻辑详解

A. 标准化线段方向 (Normalization)

为了方便 for 循环的编写（通常习惯从小到大遍历），需要保证起点 x 坐标小于等于终点 x 坐标。

if (ux[i] > vx[i]) {
    swap(ux[i], vx[i]); // 保证 x 方向是从左向右
    swap(uy[i], vy[i]); // y 随之交换
}

B. 计算整数点步长 (Step Calculation) —— 重点！

这是之前代码出错的地方。我们需要算出从当前点走到下一个整数点，x 和 y 分别要加多少。

• 公式：

  g = \text{abs}(\text{gcd}(dx, dy))

  \text{step}_x = dx / g

  \text{step}_y = dy / g

• 为什么必须加 abs？

  • dx 既然已经保证非负（因为交换了 ux, vx），但 dy 可能是负数（斜率向下）。

  • C++ 的 gcd 函数对负数的处理结果可能是负数。

  • 如果 g 是负数，那么 step_x = dx / g 就会变成负数。

  • 导致 for 循环 x += step_x 实际上在减小 x，永远无法达到 x <= vx 的终止条件，造成死循环或逻辑错误。

C. 哈希与统计 (Hashing & Counting)

• 自定义 Hash：x * 1000003 + y。

  • 注意：这种写法在 x, y 很大时容易溢出 int 或产生冲突。竞赛中通常建议用 pair<int,int> 作为 map 的键，或者使用 long long。

• 巧妙的计数判定：

  if (++mp[_hash(x, y)] == 2) ans++;

  • 只有当计数器正好变成 2 时才统计。

  • 如果该点被第 3、第 4 条线段覆盖，mp 值会变成 3, 4，条件不满足，从而避免了重复计算。

4. 易错点复盘 (Pitfalls)

错误点	现象	原因	解决方案
GCD 符号问题	死循环 / TLE	斜率为负时，gcd 返回负数，导致 x 步长变为负，循环方向反了。	int g = abs(gcd(dx, dy)); 强制分母为正。
Hash 冲突	WA (答案错误)	不同的 (x,y) 算出了相同的 hash 值。	增大乘数系数，或改用 map<pair<int,int>, int>。
垂直线段处理	逻辑遗漏	垂直线段 dx=0，gcd(0, dy) 结果为 dy，除法逻辑依然成立，但通常单独处理更清晰。	代码中用了 if (ux != vx) 分支单独处理垂直线（也可统一处理）。

5. 复杂度分析

• 时间复杂度：O(\sum \text{Length} \times \log(\text{Points}))。

  • 外层循环遍历线段。

  • 内层循环遍历线段上的点（长度）。

  • map 的操作是 \log N 级别的。

• 空间复杂度：O(\text{Points})，取决于被覆盖的整数点总数。