wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
计算几何基础
? 知识点 ?
? 计算几何 ?
2017-03-19 19:23:51
804
1
0
wuvin
? 知识点 ?
? 计算几何 ?
快省选滚粗了,来总结一下计算几何 计算几何是著名的口上A着快,写出来各种拿不到分,大坑小坑满天飞(做过的所有计算几何题只有两道1A了。所有计算几何几乎没法调试,没法对拍)。 所以在这里总结一下类型,先从基础讲起。信息学的几何和数学的几何有很大不同,由于有强大的计算能力所以一般直接爆算就是了,什么梅尼劳斯、费马点之类的公式完全用不上,暴力不解释。由于要解析几何,使用向量特别多,比如空间中一条直线,能用向量两点式就不用y=kx+b,为什么?k计算时会爆啊inf...,暴了就WA了。 向量的使用有极大的优势,可以不用区分象限什么的,面积叉积就好了,由于有了向量,什么距离面积都可以是负的,极大地统一了公式尽量免去了分类讨论与细节。 --- ##叉积 不支持交换律,A×B=a.x*b.y-b.x*a.y,就是由ABO所形成的三角形的面积的两倍(B在OA左侧为正,反之为负),至于证明。。。网上多的是。用来判断直线与点的位置关系用得最多。比如poj2318。用来求面积也有,比如bzoj1132。 ##极角 也就是向量与X轴正方向的夹角,这个可比数学好用多了,比如两角之和的cos值怎么求?和角公式?直接暴力atan2、acos、asin求出角度相减就是,然后再求一个cos,这时终于感到cmath库的强大了。例:bzoj1419. ##向量旋转 可以如上方所述暴力,但暴力较慢,如果旋转操作特别多的话还是手推和差角公式转一转。练习题目poj3845。还有一道旋转玄学bzoj3707。(顺带附上一句bzoj3707的方法在有三点共线的情况下是错的别问我是怎么知道的,不过此题不影响,反正是0,只是这个方法不能用来求最大三角形面积。) ##直线相交 向量两点式配合面积倒一倒来求交点还是很兹糍的,草稿纸上手玩一下就好了,不过要考虑到特殊情况才行。比如这几种情况 ![](http://imglf2.ph.126.net/qx44JUiPFZfmEazFuMo4BA==/6598253940740573294.png) ``` inline point get_inter(const seg &a,const seg &b){ long double p1=-cross(dec(a.b,a.a),dec(b.b,a.a)); long double p2=cross(dec(a.b,a.a),dec(b.a,a.a)); return (b.b-b.a)*(p2/(p2+p1))+b.a; } ``` 例题:poj2653 (数据弱请放心暴力,如有神犇可以不暴力比如mlogm请评论区打脸) 以下使一些常见图形的技巧:正方形两点hash——poj2002,圆——SGU198 <font size=1>2016-04-05</font>
上一篇:
SCOI2016酱油记
下一篇:
中级数据结构
1
赞
804 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
没有帐号? 立即注册