Posted on 2007-05-25 23:33
oyjpart 阅读(1676)
评论(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 注意根据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的方程 根据A点坐标求出AB的方程 再求出AB与L的交点Y 接着就是A' = 2 * Y - X
7.求50000个点的最远距离 先用NlogN的算法求凸包 再枚举点距
8.判断一个点是否在一个多边形内 可以沿这个点做一条射线 然后判断这个点与其他边的交点的个数 如果是偶数则在外部 如果为奇数 则在里面 如果在边界 可以用点线距为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 则可以现用maxy[x], miny[x]来保存纵坐标的最大值 和 最小值 显然只有这些点才可能出现在凸包上面 然后使用Graham-Scan算法按横坐标从小到大排序求凸包即可（蓝书P8） 这样排序的时间从nlogn 变成N
1.怎样由凸包上面的点确定最大的三角形面积？
枚举每一个点a
定下b点为a+1 c为a+2
移动c点直到面积不再增加（因为是凸多边形 故面积呈现先增后减序列）
移动b点在a，c之间 直到面积不再增加