※ 引述《euph (咬咬嚼嚼猴子口味)》之铭言：
: 感谢这么专业的回答
: 其实被大家猜中了 这只是其中一个我卡住的问题
: leader给我的题目是更复杂的问题
: 只是我不好意思全贴出来 这样感觉好像在作弊 ＸＤＤＤ
: 简单描述一下题目好了
: 已知在二元平面里有Ｎ个点 还有一个从原点的视角角度为alpha
: 求这视角在什么情况下可以包含最多的点
: 大致上的算法是写得出来的
: 只是leader说可以达到O(N) 而且除了利用arctan以外有更快速的计算方法
: 我目前想到是将所有的点计算出角度之后
: mapping到一个0~2pi的线段上然后再求最大值
: 所以才会想说要如何计算这角度 比较省复杂度
: 抱歉 一开始没有把问题说清楚 :(
不需要把角度真的通通求出来.
令 y>=0 的点的集合为 V1, y<0 的点为 V2,
sort V1 by - ( v * (1, 0) / | v | ) # * === inner product
sort V2 by ( v * (1, 0) / | v | )
let V = concat ( V1, V2 )
然后用两个 iterator i, j,
把 V 扫一遍, compare ( V[i] * V[j] / |V[i]||V[j]| ) 与 cos ( alpha ),
夹角 < alpha 时 j++, count++
> alpha 时 i++, count