【OI之路】07其他-6计算几何

计算几何
more1
more2

辅助函数

1
double atan2(double x,double y)

向量相关

见线性代数一章

坐标(向量)旋转:
这个很好推,$(a,b)逆时针旋转 \theta ->(acos\theta -bsin\theta ,asin\theta +bcos\theta )$

三角形的五心

外心:垂直平分线交点

重心:中线交点,重心到顶点=2*重心到对边中点,平分面积,到三个顶点距离的平方和最小,坐标为平均数,到三个顶点的向量和=零向量

垂心:垂线交点,三角形垂心到任一顶点=2*其外心到对边,单位圆上为三点坐标之和

内心:角平分线交点,直角三角形内心的$r=\frac{a+b-c}{2}$,圆内三点的三角形内心=那三段圆弧的中点形成三角形的垂心

欧拉线:外心O,重心G,垂心H,三点共线,2OG=GH

几何图形

求多边形(可以凹)的面积
相邻两点(逆时针的话,可以不用绝对值,所以能模了,尽管面积可能是负数,最后总是正数)到坐标原点的叉积和
例题:HDU-2036

随机任意多边形的数据
[Wf2017]Airport Construction

直线交点
建议画图,一条直线与另外两点的叉积面积比=高的比=另一条直线被交点所分的两部分之比

1
2
3
4
5
6
7
Pt check(Pt a,Pt b,Pt c,Pt d)//尚未验证正确性
{
Pt t1=b-a,t2=d-c,t3=c-a;
ll A=cross(t1,t2),B=cross(t3,t2);
double xx=a.x+(double)B/A*t1.x,yy=a.y+(double)B/A*t1.y;
return (Pt){xx,yy};
}

过圆外一点的切线:求点与圆心的直线然后用asin旋转

好题

雅礼冬令营集训2019 D7t3

转载

尚未学习

y>=kx+b(y<=kx+b同理)的半平面交的并集是一个上凸壳,我们可以把它对偶成凸包,即是将一条直线的 (k,b)视为一个点 (k,b),然后做一个下凸壳。这样我们就可以合并半平面交了,即为做这个对偶凸包的闵可夫斯基和(就是(a,b)和(c,d)合并起来后为(a+b,c+d)。因为ax+b+cx+d=>(a+c,b+d))。而闵可夫斯基和可以双指针在两个凸壳上面移动来解决,开始时候,两个指针p1,p2都在1位置,之后判断(p1,p2+1),(p1+1,p2)和(p1,p2)的斜率哪个更大(叉积判断即可),以此来移动指针,这样相当于直接扔掉了一列或者一行。

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/7158.html
转载请注明出处,谢谢!