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

计算几何

点积(向量乘积): $|a||b| cos \theta=x1x2+y1y2$
几何意义为b在a方向上的投影
垂直:点积=0

两个向量的叉乘,又叫向量积、外积、叉积
是一个向量,与【两个向量所在平面】垂直
$x1y2-x2y1$
方向:右手法则,四指从a到b,大拇指的朝向
几何意义为平行四边形的面积

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

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

oth

直线交点

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};
}

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