计算几何基础

快省选滚粗了，来总结一下计算几何

计算几何是著名的口上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

wuvin

导航

最近发表

友情链接