oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6
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之间 直到面积不再增加
    

Feedback

# re: 总结一下最近做的计算几何学到的知识  回复  更多评论   

2007-05-28 13:25 by eyye
我对凸包算法很感兴趣,我正在做的Plot3D ( http://eyye.cnblogs.com )在构造多面体时就是在进行凸包计算。

# re: 总结一下最近做的计算几何学到的知识  回复  更多评论   

2007-05-28 14:54 by oyjpart
呵呵 确实好玩 不过我不是很懂。。呵呵~~

# re: 总结一下最近做的计算几何学到的知识  回复  更多评论   

2007-06-10 12:39 by 星梦情缘
凸包是什么啊,我是新手,楼主能解释一下吗???

# re: 总结一下最近做的计算几何学到的知识  回复  更多评论   

2007-06-10 17:54 by oyjpart
我的理解很粗浅哎 我觉得就是对于平面内离散的点集S
凸包就是S的一个子集S1形成的一个凸多边形 使所有的点都包含在这个凸包C或在C的边上

# re: 总结一下最近做的计算几何学到的知识  回复  更多评论   

2007-08-12 18:16 by mb
楼主,最后一个三角形面积能解释一下吗?为什么这么做就行了?

# re: 总结一下最近做的计算几何学到的知识  回复  更多评论   

2007-08-13 09:18 by oyjpart
就是因为凸多边形是凸的 所以如果你确定两点移第三点会出现先增后减

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理