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

计算几何
more1
more2

辅助函数

1
double atan2(double x,double y)

向量相关

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

点积(内积、数量积):
满足交换律、结合律
$|a||b| cos \theta=x1x2+y1y2$
几何意义为b在a方向上的投影
垂直:点积=0

叉积(向量积、外积、叉乘):
满足结合律不满足交换律
是一个向量,与【两个向量所在平面】垂直
$模长=|a||b|sin \theta=x1y2-x2y1$
方向:右手法则,四指从a到b,大拇指的朝向,向上为正
几何意义为有向的平行四边形的面积

几何图形

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

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