当前位置：首页 > news >正文

离散化遍历

news 2026/3/26 22:10:58

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

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

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

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

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

这是之前代码出错的地方。我们需要算出从当前点走到下一个整数点，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 的终止条件，造成死循环或逻辑错误。

自定义 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，条件不满足，从而避免了重复计算。

错误点	现象	原因	解决方案
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)` 分支单独处理垂直线（也可统一处理）。

时间复杂度：$O(\sum \text{Length} \times \log(\text{Points}))$。
- 外层循环遍历线段。
- 内层循环遍历线段上的点（长度）。
- map 的操作是 $\log N$ 级别的。
空间复杂度：$O(\text{Points})$，取决于被覆盖的整数点总数。