ACM计算几何模板（模板）

女爷i 2022-09-25 06:29 168阅读 0赞

1. 判断空间三点共线

点的储存方式：

![点的储存方式：][20160815210651828]

判断空间三点共线 假设三点为p\[i\] p\[j\] p\[k\]

方法1(推荐)：

原理：共线两向量成比例 即 x2/x1=y2/y1=z2/z1

![这里写图片描述][20160815210541093] ![这里写图片描述][20160815210946855]

方法2：利用点积求cos角

![这里写图片描述][20160815211223499]

方法3：利用中间点到外边两点距离和等于外边两点距离和

2.判断四点能否组成四面体

点的储存方式：

![点的储存方式：][20160815210651828]

只要判断组成的四面体体积是否为0即可。

四面体体积为为四点组成的三个向量的混合积除以6。

设四点分别为 p\[i\] p\[j\] p\[k\] p\[l\]

LL为long long

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FeqE0G1v-1613976880242)(https://img-blog.csdn.net/20160815213708747)\]

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v9rQvY8t-1613976880246)(https://img-blog.csdn.net/20160815213734518)\]

3.点积与叉积概要

点积就是 p1\*p2=x1\*x2+y1\*y2  
也是 p1\*p2=|p1|\*|p2|\*cosθ  
叉积就是 p1×p2=x1\*y2-x2\*y1  
也是 p1×p2=|p1|\*|p2|\*sinθ

所以一些在数学上需要用sin或者cos的都可以用点积或者叉积来判断

这里需要注意： 角度是按逆时针来计算的

如计算点积，角度是向量p1逆时针转到p2的角度

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qtTHhNQD-1613976880250)(https://img-blog.csdn.net/20160815222655958)\]

如计算叉积，角度同样是p1 逆时针旋转到p2的角度  
\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vcRUrMRC-1613976880253)(https://img-blog.csdn.net/20160815222818460)\]

比如判断点q在直线p1 p2 上，就是角度为0或者180度，用sin来判断，所以用叉积，如果要再判断q是否在线段p1 p2上，假设在线段p1 p2内，则p1q 和p2q的θ应为180度，用cosθ小于等于0判断即可。

比如计算向量p1逆时针方向的\[0,90)度的点就是sinθ大于等于零，cosθ大于0，相应的使用叉积与点积。

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VUsMUKhn-1613976880255)(https://img-blog.csdn.net/20160815223720415)\]

在\[90,180）之间的就是sinθ大于等于，cosθ小于等0  
\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TTEuRmF4-1613976880256)(https://img-blog.csdn.net/20160815223842884)\]

[20160815210651828]: /images/20220718/af0c34902c2649758bf58b9c1f4b2e6d.png
[20160815210541093]: https://img-blog.csdn.net/20160815210541093
[20160815210946855]: /images/20220718/8cf40a07de014f55ba398b8cd2778ab2.png
[20160815211223499]: /images/20220718/a51dc70f3f6b41ce87974954995f96d9.png