叉积在ACM中的应用
定义
若OA → =(x 1 ,y 1 ) OB → =(x 2 ,y 2 ) OA→=(x1,y1) OB→=(x2,y2)
定义叉积：OA → ×OB → =x 1 y 2 −x 2 y 1 OA→×OB→=x1y2−x2y1
性质
-
S △OAB =12 |OA → ×OB → | S△OAB=12|OA→×OB→|
如图是一种简单情况，叉积表示的面积即最大的矩形面积减去P 1 P 2 T 3 P1P2T3所构成的矩形面积。又T 4 =S 4 T4=S4，即要证2(T 1 +T 2 +T 3 )=S 1 +T 1 +S 2 +T 2 2(T1+T2+T3)=S1+T1+S2+T2又已知S 1 +P 1 =T 1 +T 3 +P 2 ,and S 2 +P 2 =T 2 +T 3 +P 1 S1+P1=T1+T3+P2,and S2+P2=T2+T3+P1两式左右相加即证。
另外的情况也可利用面积的加减证明。 已知直线上的两点s、e，可以求出ax+by+c=0的参数
a = s.y-e.y;
b = e.x-s.x;
c = s× ×e;
应用
1. 判断点与直线的相对位置
在直线上取两点P，Q，构成直线的方向向量PQ → PQ→。需要判断的点A构成AP → 、AQ → AP→、AQ→两个向量。则规定AP → ×AQ → AP→×AQ→的符号反映了点与直线的相对位置。当值为0时A在直线PQ上。
2. 判断线段与直线的位置关系
在直线外的两个点分别作应用1中的叉积操作，若得到的结果同号则在同侧，异号则在异侧。
POJ 3304：原题等价为是否存在一条直线（投影路径）与所有的线段相交
POJ 1039：求从管子的一端到最远到达哪里。暴力枚举所有可能的光线方向，与管子端点相交、与管重合均可穿过。需注意光线虽与管子不相交但超出管子的情况。
3. 判断直线与直线的位置关系
有以下两种方法。
- 容易理解的是利用性质2，得到直线方程a 1 x+b 1 y+c 1 =0与a 2 x+b 2 y+c 2 =0 a1x+b1y+c1=0与a2x+b2y+c2=0。当a 1 b 2 =a 2 b 1 时 a1b2=a2b1时，直线平行（特判重合的情况）；否则两直线相交，直接解得x=−c 1 b 2 +c 2 b 1 a 1 b 2 −a 2 b 1 x=−c1b2+c2b1a1b2−a2b1
- 分别在直线上取两点，类似于应用2，将其中一条作为基准直线，得到两个叉积结果。若都为0，则两直线重合。若两者不为0且值相等，则两直线平行。否则相交。
用叉积，而不是求出斜率，这样能避免斜率不存在的情况。
POJ 1269：过滤掉前两种情况后，求直线的交点坐标时再列出直线方程(ax+by+c=0)求解。
4. 判断线段与线段的位置关系
线段1、2所在的直线为3、4，则当1、4与2、3均相交时可得两线段相交，否则不相交。也可以根据题目条件简化其一，视条件而定。
注意：要做四组初始判断避免两线段共线但不相交的误判。 注意：要做四组初始判断避免两线段共线但不相交的误判。
也被称为跨接条件。即线段相交必须满足线段1的左端点在线段2的右端点的左边，其余三个方向同理。
POJ 1556：枚举任意两个端点是否存在直线通道时，需判断该线段与其余的竖直线段是否相交。
POJ 2653：该break时就break，否则T无休……
POJ 3449：差不多可以当作模拟题来做。
CF 589D：可以抽象成线段来做。
5.判断多边形是否是凸包
顺次给出多边形的点{p i } {pi}判断其是否构成凸包。由于不知道是顺时针还是逆时针给出的，所以先记录一组(p 1 −p 0 )×(p 2 −p 1 ) (p1−p0)×(p2−p1)的符号作为基准。之后每组(p i+1 −p i )×(p n+2 −p n+1 ) (pi+1−pi)×(pn+2−pn+1)的符号都与之比对，若异号，则不为凸包。
注意：若题意允许三点共线，则先找到第一个非0的符号，再进行判断。并且允许有0存在。
6.判断点是否在凸多边形内
- 先特判点O是否在边上（可利用叉积为零）。
- 将点O作为顶点，顺次连接多边形的端点，得到n个角度。用叉积顺次得到各个角度的符号，若全部同号则点在凸多边形内。否则不在凸多边形内。
POJ 1584：先判断给出的点是否构成凸包，再判断圆心是否在凸包内，再看是否能容纳下这个圆。