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