计算几何

学习笔记 题单

点积

$dot(A,B)=A.x*B.x+A.y*B.y$

叉积

$cross(A,B)=A.x*B.y-A.y*B.x$
这个东西也是向量围成的三角形的有向面积的两倍.

转角公式

$(y,x)$=$(sin{\theta}r,cos{\theta}r)$
$(sin{\theta+\beta}r,cos{\theta+\beta}r)=((sin{\theta}cos{\beta}+cos{\theta}sin{\beta})r,(cos{\theta}cos{\beta}-sin{\theta}sin{\beta})r)$
然后带进去就得到:
$(x,y)->(xcos{\beta}-ysin{\beta},xsin{\beta}+ycos{\beta})$

极角排序

atan2

直接用一个$ang$表示极角=$atan2(y,x)$;

叉积

不是很会,极角排序用的也少.

直线夹角

你把一个看成坐标轴从O开始,另一个直接按照tan算一下就好了.

直线交点

等分点算,具体挖坑.

判断线段是否相交

还算好吧.跨立实验搞一下就好了.
就是把那个平行四边形搞出来,然后判断一下,两端点和另外一条线段两条点的叉积都不同号就相交.

凸包-Graham扫描法

考虑把点按照$x,y$排序,然后显然第一个是在凸包里面的,然后正反扫一遍求一个上凸壳求一个下凸壳就可以了.
话说这个好像是变种,叫做$Andrew$.不清楚了

判断点是否在凸多边形内

引几条射线就好了,然后rand一下旋转角度再判断一下.

判断点是否在凸包内

极角判断一下就好了,注意$A[1]=(0,0)$而且需要首先判断一下是否在边界外面.

求多边形面积

直接求一个凸包然后按照顺序叉积算面积再/2就是答案

三角形重心

三坐标平均值就是答案.

半平面交

不会

最小圆覆盖

random_shuffle+看上去是$O(n^3)$实际上是$O(n)$的判断就好了.

旋转卡壳

不会(不仅不会而且不会读)

自适应Simpson法

拿个公式套进去就好了.
用于不是很好求原函数的时候求积分的做法.

闵可夫斯基和

定义两个凸包的和为:
$A+B={(x_i^A+x_j^B,y_i^A+y_j^B ):(x_i^A,y_i^A )\in A,(x_j^B,y_j^B )\in B}$
那么要在这个凸包和上面搞一些事情...
怎么做呢?
这就要用到$Minkowski$这个高级东西了...
考虑$x_1+y_1$一定是在和里面的.
然后因为凸包本来就是按照一定的顺序搞的,那么显然可以一个一个的插入,然后每次插入判断一下那边更优就好了.
代码实现