CST PA1
1-2 A+B Graphics
算法构思
容易想到先将横轴和纵轴的端点进行排序预处理, 进而确定 $n$ 条线段的具体端点. 通过二分查找, 对于其中每条线段使用 ToLeft 测试来判断其与所给出点 $P$ 和原点 $O$ 的连线段 $OP$ 是否有交点, 高效查找出临界交点, 进而确定总交点的数目.
进行ToLeft 测试判断两条直线是否有交点, 可以先算出 $n$ 条线段相应横纵坐标乘积并存储, 以便进行 ToLeft 测试时无需重复计算, 优化算法时间性能.
由于端点坐标数据范围为 $[1, 2^{31})$, 选用 $\text{long long}$ 数组来存储坐标与相应乘积; 二分查找时对于几种临界情况进行了特殊处理与返回, 主要包含全无交点与全部交点两种情况.
参考资料
对 $x$ 轴和 $y$ 轴上的点坐标进行排序主要参考了此文章, 选择了 <stdlib.h> 中的 qsort() 函数;
复杂度估计
数据输入过程的时间复杂度为 $O(n)$; 数据排序过程的时间复杂度为 $O(nlogn)$.
而算法时间复杂度主要来自二分查找交点的过程:
...
// Line 13
// cross 函数返回与线段 OP 存在交点的最上方线段标号.
int cross (...) {
if (n == 1) {
...
}
else {
int low = 0;
int high = n - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
...
}
}
return -1;
}
...其中每经过一次 while 循环都要访问若干次 toleft 函数, 此函数调用的时间为常数时间, 因此 cross 函数的时间复杂度与二分查找相同, 为 $O(logn)$.
进而对于 $n$ 条线段信息的输入, 进行 $m$ 次查询, 算法的时间复杂度为 $O(mlogn)$.
算法空间复杂度主要来自存储横纵坐标与相应乘积的过程:
...
long long x[n] = {0};
long long y[n] = {0};
long long z[n] = {0};
...正比于输入数据的数目, 对于 $n$ 条线段信息的输入, 算法的空间复杂度为 $O(n)$.
