Posted on 2007-05-25 23:33
oyjpart 閱讀(1697)
評論(6) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
1.點積Dot Product Cos(θ) = (A ⋅ B)/(|A||B|) so we can get angle θ by acos function , θ 是A，B的夾角 沒有正負
2.叉積Cross Product A x B = |A||B|Sin(θ) , θ 的正負由A，B的右手定則決定
其值同時代表A,B形成的平行四邊形的面積
3.線段與點之間距離Line-Point Distance L = | (AB x AC)/|AB| |其中L是從C到A,B這條直線的距離 因為AB x AC/2是ABC形成的三角形面積 而三角形面積也等于|AB|*L/2 注意根據(jù)cross product的定義 L值應該取絕對值
4.求垂直平分線 首先構造AB的方程 Ax+By=C 則平分線方程為 -Bx+Ay=D 把AB的中點代入進去就得到了D
5.求3點共圓 A,B,C 首先做出 AB 和 BC的平分線 求出交點o 則交點o就是圓心 而 dis(o, B)就是半徑
6.求點A相對一直線L的對面點B 首先得到AB的方程 根據(jù)A點坐標求出AB的方程 再求出AB與L的交點Y 接著就是A' = 2 * Y - X
7.求50000個點的最遠距離 先用NlogN的算法求凸包 再枚舉點距
8.判斷一個點是否在一個多邊形內 可以沿這個點做一條射線 然后判斷這個點與其他邊的交點的個數(shù) 如果是偶數(shù)則在外部 如果為奇數(shù) 則在里面 如果在邊界 可以用點線距為0來判斷
9.球坐標轉化成立體坐標
double x = sin(lng/180*PI)*cos(lat/180*PI)*alt;
double y = cos(lng/180*PI)*cos(lat/180*PI)*alt;
double z = sin(lat/180*PI)*alt；
2.關于凸包的題目
gift-Wrapping算法復雜度O(n^2)很慢
Gram-Scan算法復雜度為O(NlogN) 但是極角序存在一些問題 所以最好寫成水平序
Melkan算法是對于多邊形的凸包算法 效率為O(N) 但是對于點集首先要用排序將其轉化成多邊形(復雜度為(NlogN)) 不實用
如果點是有限制的 比如0 <= x,y <= N 則可以現(xiàn)用maxy[x], miny[x]來保存縱坐標的最大值 和 最小值 顯然只有這些點才可能出現(xiàn)在凸包上面 然后使用Graham-Scan算法按橫坐標從小到大排序求凸包即可（藍書P8） 這樣排序的時間從nlogn 變成N
1.怎樣由凸包上面的點確定最大的三角形面積？
枚舉每一個點a
定下b點為a+1 c為a+2
移動c點直到面積不再增加（因為是凸多邊形 故面積呈現(xiàn)先增后減序列）
移動b點在a，c之間 直到面積不再增加