※ 引述《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