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