※ 引述《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-- 然後 j 前进到 V.end 的时候要从 j=V.begin 绕过来继续, 直到 i == V.end 这样只需要一个cosine, 其他都是乘法除法. 但是这样需要排序, 我一时想不出O(N)耶, 有人知道吗? : ※ 引述《DJWS (...)》之铭言： : : 这个问题可以从很多层面来看 : : 1. 数学层面: 也许你需要的是一个更好的数学性质、计算公式。属於解析几何领域 : : http://stackoverflow.com/questions/2150050/ : : 2. 程式层面: 也许你想找一个方便的程式语言、方便的library。属於软体开发领域 : : 　http://stackoverflow.com/questions/3121139/ : : 3. 硬体层面: 也许你好奇的是硬体效能、能不能用组语加速。属於组合语言领域 : : 　http://stackoverflow.com/questions/2479517/ : : 4. 演算法层面: 也许你需要的是一个更好的 arctan 演算法以及实作。属於数值方法领域 : : http://stackoverflow.com/questions/23047978/ : : 5. 专案层面: 也许你该考量：研究太过细节的东西，是否符合成本效益？属於专案管理领域 : : 6. 社交层面: 也许是你的主管吹毛求疵，而你又不知道如何跟他说？属於社交心理学领域 : : 所以你主管究竟需要什麽？ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.170.157.157 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1403500621.A.5A1.html ※ 编辑: neutrino (118.170.157.157), 06/23/2014 13:17:18 ※ 编辑: neutrino (118.170.157.157), 06/23/2014 13:18:14 ※ 编辑: neutrino (118.170.157.157), 06/23/2014 13:18:35