計(jì)算幾何是算法競(jìng)賽的一大塊，而叉積是計(jì)算機(jī)和的基礎(chǔ)。

首先叉積是計(jì)算說(shuō)向量之間的叉積，那么我們可以這樣定義向量，以及向量的運(yùn)算符重載。

叉積求面積： (b.x - a.x) * (c.y - a.y) - (b.y - a.y)*(c.x - a.x)

[cpp]?view plaincopyprint? struct?Point?? {?? ????double?x,y;?? ????Point(double?x=0,double?y=0):x(x),y(y)?{}?? };?? typedef?Point?Vector;?? Vector?operator?+?(Vector?A,Vector?B)?{?return?Vector(A.x+B.x,A.y+B.y);?}?? Vector?operator?-?(Vector?A,Vector?B)?{?return?Vector(A.x-B.x,A.y-B.y);?}?? Vector?operator?*?(Vector?A,double?p)?{?return?Vector(A.x*p,A.y*p);?}?? Vector?operator?/?(Vector?A,double?p)?{?return?Vector(A.x/p,A.y/p);?}?? ?? bool?operator?<?(const?Point&?a,const?Point&?b)?? {?? ????return?a.x<b.x?||?(a.x==b.x?&&?a.y<b.y);?? }?? int?dcmp(double?x)??//?? {?? ????if(fabs(x)<esp)?return?0;?? ????else?return?x<0?-1:1;?? }?? bool?operator?==?(const?Point&?a,const?Point&?b)?? {?? ????return?dcmp(a.x-b.x)?==?0?&&?dcmp(a.y-b.y)==0;?? }??

首先在二維坐標(biāo)下介紹一些定義：

點(diǎn)：A（x1，y1），B（x2，y2）

向量：向量AB=（ x2 - x1 , y2 - y1 ）= ( x , ?y );

向量的模 |AB| = sqrt ( x*x+y*y );

向量的點(diǎn)積：?結(jié)果為 x1*x2 + y1*y2。

點(diǎn)積的結(jié)果是一個(gè)數(shù)值。

點(diǎn)積的集合意義：我們以向量 a 向向量 b 做垂線，則 | a | * cos（a,b）為 a 在向量 b 上的投影，即點(diǎn)積是一個(gè)向量在另一個(gè)向量上的投影乘以另一個(gè)向量。且滿足交換律

應(yīng)用：可以根據(jù)集合意義求兩向量的夾角，cos（a,b） =（ 向量a * 向量b ） / （| a | * | b |） =??x1*x2 + y1*y2 /?（| a | * | b |）

向量的叉積：?結(jié)果為 x1*y2-x2*y1

叉積的結(jié)果也是一個(gè)向量，是垂直于向量a，b所形成的平面，如果看成三維坐標(biāo)的話是在 z 軸上，上面結(jié)果是它的模。

方向判定：右手定則，（右手半握，大拇指垂直向上，四指右向量a握向b，大拇指的方向就是叉積的方向）

叉積的集合意義：1：其結(jié)果是a和b為相鄰邊形成平行四邊形的面積。

2：結(jié)果有正有負(fù)，有sin（a，b）可知和其夾角有關(guān)，夾角大于180°為負(fù)值。

3：叉積不滿足交換律

應(yīng)用：

1：通過(guò)結(jié)果的正負(fù)判斷兩矢量之間的順逆時(shí)針關(guān)系

若 a x b > 0表示a在b的順時(shí)針?lè)较蛏?/p>

若 a x b < 0表示a在b的逆時(shí)針?lè)较蛏?br />

若 a x b == 0表示a在b共線，但不確定方向是否相同

2：判斷折線拐向，可轉(zhuǎn)化為判斷第三點(diǎn)在前兩的形成直線的順逆時(shí)針?lè)较?，然后判斷拐向?/p>

3：判斷一個(gè)點(diǎn)在一條直線的那一側(cè)，同樣上面的方法。

4：判斷點(diǎn)是否在線段上，可利用叉乘首先判斷是否共線，然后在判斷是否在其上。

5：判斷兩條直線是否想交（跨立實(shí)驗(yàn)）

根據(jù)判斷點(diǎn)在直線那一側(cè)我們可以判斷一個(gè)線段的上的兩點(diǎn)分別在另一個(gè)線段的兩側(cè)，當(dāng)然這是不夠的，因?yàn)槲覀儺媹D發(fā)現(xiàn)這樣只能夠讓直線想交，而不是線段，所以我們還要對(duì)另一條線段也進(jìn)行相同的判斷就ok。

代碼：

[cpp]?view plaincopyprint? ///計(jì)算點(diǎn)積，及向量長(zhǎng)度，及向量夾角?? double?Dot(Vector?A,Vector?B)?{?return?A.x*B.x+A.y*B.y;?}?? double?Length(Vector?A)?{?return?sqrt(Dot(A,A));?}?? double?Angle(Vector?A,Vector?B)?{?return?acos(Dot(A,B))/Length(A)/Length(B);?}?? //計(jì)算叉積，向量逆時(shí)針旋轉(zhuǎn),兩線段是否想交?? double?Cross(Vector?A,Vector?B)?{?return?(A.x*B.y-A.y*B.x);?}?? double?Area2(Vector?A,Vector?B,Vector?C)??{?return?Cross(B-A,C-A);?}?? Vector?Rotate(Vector?A,double?rad)?? {?? ????return?Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));?? }?? bool?Converxline(Vector?A,Vector?B,Vector?C,Vector?D)?? {?? ????//共線或平行?? ????if((Area2(A,B,C)==0&&Area2(A,B,D)==0)?||?Area2(A,B,C)*Area2(A,B,D)>0||Area2(C,D,A)*Area2(C,D,B)>0)?? ????????return?false;?? ????else?? ????????return?true;?? }