请结合这篇题解一起食用
题意解析:
给定一个平面直角坐标系和 nnn 个点 ,第 iii 个点的坐标 (xi,yi)(x_i,y_i)(xi ,yi )
有 qqq 次查询,每次给出两个点的编号 (aj,bj)(a_j,b_j)(aj ,bj ) ,有一条射线从原点出发,初始时指向编号为 aja_jaj 的点,绕原点顺时针旋转,直到恰好指向编号为 bjb_jbj 的点停止
在整个旋转过程中(包括初始和最终时刻),只要射线朝向某个方向,处在该方向上的所有点都会被瞬间“击中”。求旋转过程中,总共会被击中的点的数量
特殊情况
不同的点可以位于从原点出发的同一方向(即共线)。在这种情况下,它们会被视为同时被击中。
如果点 aja_jaj 和 bjb_jbj 位于从原点出发的同一方向,则射线无需旋转,只击中该方向上的所有点。
数据范围:
2≤n≤2×1052\leq n \leq2\times10^52≤n≤2×105
1≤q≤2×1051\leq q \leq2\times10^51≤q≤2×105
−109≤xi,yi≤109-10^9\leq x_i,y_i \leq10^9−109≤xi ,yi ≤109
(xi,yi)≠(0,0)(x_i,y_i)\neq(0,0)(xi ,yi )=(0,0)
1≤aj,bj≤n1\leq a_j,b_j \leq n1≤aj ,bj ≤n
aj≠bja_j\neq b_jaj =bj
预处理部分:
对每个怪物坐标 (xi,yi)(x_i, y_i)(xi ,yi ) ,使用三角函数arctanarctanarctan(对边:邻边)
计算其相对于原点 (0,0) 的极角(弧度)。使用 long double 保证精度。
为了方便后续查询,将 atan2latan2latan2l 输出的 (−π,π](-π, π](−π,π] 范围统一调整到 [0,2π)[0, 2π)[0,2π),随后按照极角排序(arctan),利用unordered_map建立原本节点编号和排序后节点的映射关系
查询部分:
先根据unordered_map查找起始节点与结束节点的图上位置
因为我没有构造环形数组,因此分为两种情况:
起始节点的arctanarctanarctan比结束节点的arctanarctanarctan大(需跨越数组边界),则查询结果为在数组中arctanarctanarctan大于等于起始节点的arctanarctanarctan的数量加上arctanarctanarctan小于等于结束节点的arctanarctanarctan的数量
起始节点的arctanarctanarctan比结束节点的arctanarctanarctan小或相等(无需跨越数组边界),则查询结果为在数组中arctanarctanarctan大于等于起始节点的arctanarctanarctan的数量减去arctanarctanarctan大于结束节点的arctanarctanarctan的数量
最终代码:
时间复杂度:O((n+q)logn)O((n + q) log n)O((n+q)logn)
空间复杂度:O(n)O(n)O(n)