題目：

經(jīng)過激烈的爭奪，Lele終于把那塊地從Yueyue的手里搶了回來。接下來，Lele要開始建造他的灌溉系統(tǒng)。

通過咨詢Lele的好友——化學系的TT，Lele決定在田里挖出N條溝渠，每條溝渠輸送一種肥料。

每條溝渠可以看作是一條折線，也就是一系列線段首尾連接而成(除了第一條線段開頭和最后一條線段的結(jié)尾)。由于溝渠很細，你可以忽略掉它的寬度。

由于不同的肥料之間混合會發(fā)生化學反應，所以修建的溝渠與溝渠之間不能相交。

現(xiàn)在TT給Lele畫了一些設(shè)計圖，Lele請你判斷一下設(shè)計圖中的溝渠與溝渠之間是否有相交。

Input

本題目包含多組測試，請?zhí)幚淼轿募Y(jié)束(EOF)。
每組測試的第一行有一個正整數(shù)N(0<N<30)，表示管道的數(shù)目。接下來給出這N條管道的信息。
對于每條管道，第一行是一個正整數(shù)K(0<K<100)，表示這條管道是由K個端點組成。
接下來的K行給出這K個端點信息。每個端點占一行，用兩個整數(shù)X和Y(0<X,Y<1000)分別表示這個端點的橫坐標和縱坐標的值。

Output

對于每組測試，如果該測試管道與管道之間有相交的話，輸出"Yes"，否則輸出"No"。

Sample Input

2
2
0 0
1 1
2
0 1
1 0
2
2
0 0
1 1
2
1 0
2 1
2
3
0 0
1 1
2 1
2
2 0
3 0

Sample Output

Yes
No
No

分析：

外積，又稱叉積，是向量代數(shù)（解析幾何）中的一個概念。兩個向量v1(x1, y1)和v2(x2, y2)的外積v1×v2=x1y2-y1x2。如果由v1到v2是順時針轉(zhuǎn)動，外積為負，反之為正，為0表示二者方向相同（平行）。此外，文中涉及行例式和方程組的概念，請參閱線性代數(shù)的相關(guān)內(nèi)容。

那如何來判斷兩線段是否相交呢？

假設(shè)有兩條線段AB，CD，若AB，CD相交，我們可以確定：
1.線段AB與CD所在的直線相交，即點A和點B分別在直線CD的兩邊；
2.線段CD與AB所在的直線相交，即點C和點D分別在直線AB的兩邊；
上面兩個條件同時滿足是兩線段相交的充要條件，所以我們只需要證明點A和點B分別在直線CD的兩邊，點C和點D分別在直線AB的兩邊，這樣便可以證明線段AB與CD相交了。
那判斷兩線段是否相交與一開始提到的向量叉乘定理有什么關(guān)系呢？有，我們可以通過叉乘來證明上面說的充要條件。看下圖：

在上圖中，線段AB與線段CD相交，于是我們可以得到兩個向量AC，AD，C和D分別在AB的兩邊，向量AC在向量AB的逆勢針方向，AB×AC > 0；向量AD在向量AB的順勢針方向，AB×AD < 0，兩叉乘結(jié)果異號。

這樣，方法就出來了：如果線段CD的兩個端點C和D，與另一條線段的一個端點（A或B，只能是其中一個）連成的向量，與向量AB做叉乘，若結(jié)果異號，表示C和D分別在直線AB的兩邊，若結(jié)果同號，則表示CD兩點都在AB的一邊，則肯定不相交。

當然，不能只證明C，D在直線AB的兩邊，還要用相同的方法證明A，B在直線CD的兩邊，兩者同時滿足才是線段相交的充要條件。

不過，線段相交還有一些特殊情況：

1.只有1點相交，如下圖：

上圖中，線段AB與CD相交于C點，按照之前介紹的方法，我們可以連成兩向量AD和AC，這時候，我們發(fā)現(xiàn)，AC與AB共線，AB×AC = 0；而AB×AD < 0；兩者并不異號，可實際上仍然相交。所以當出現(xiàn)兩叉乘結(jié)果中，有一方為0，也可以看成點CD在直線AB的兩邊。

2.兩條線段重合，如下圖：

在上圖中，線段AB與線段CD重合，重合部分為CB，這種重合的情況要特殊判斷：

首先，我們給沒條線段的兩個端點排序，大小判斷方法如下：橫坐標大的點更大，橫坐標相同，縱坐標大的點更大。

排好序后，每條線段中，小的點當起點，大的當終點。我們計算向量AB×向量CD，若結(jié)果為0，表示線段AB平行CD，平行才有了重合的可能；但平行也分共線和不共線，只有共線才有可能重合，看下圖：

上圖中，第一種情況不共線，第二種情況共線。那如何來判斷是否共線呢？

我們可以在兩條線段中各取一點，用這兩點組成的向量與其中一條線段進行叉乘，結(jié)果若為0，就表示兩線段共線，如下圖：

我們?nèi)∠蛄緽C，若BC×CD = 0，表示兩點共線，即是第二種情況，否則就是第一種情況。第一種情況肯定不相交。然而，即使他們共線，卻還是不一定重合，就如上圖中第二種情況。這時候，之前給點排序的妙處就體現(xiàn)出來了：

若一條線段AB與另一條線段CD共線，且線段AB的起點小于等于線段CD的起點，但線段AB的終點（注意是終點）大于等于線段CD的起點（注意是起點），或者交換一下順序，CD的起點小于AB的起點…只要滿足其中一個，就表示有重合部分。

為方便計算，對坐標點的大小比較作如下定義：x坐標較大的點為大，x坐標相等但y坐標較大的為大，x與y都相等的點相等。一條線段中較小的一端為起點，較大的一端為終點。
兩條線段的位置關(guān)系大體上可以分為三類：有重合部分、無重合部分但有交點（相交）、無交點。為避免精度問題，首先要將所有存在重合的情況排除。

重合可分為：完全重合、一端重合、部分重合三種情況。顯然，兩條線段的起止點都相同即為完全重合；只有起點相同或只有終點相同的為一端重合（注意：坐標較小的一條線段的終點與坐標較大的一條線段的起點相同時應判定為相交）。要判斷是否部分重合，必須先判斷是否平行。設(shè)線段L1(p1->p2)和L2(p3->p4)，其中p1(x1,
y1)為第一條線段的起點，p2(x2, y2)為第一條線段的終點，p3(x3, y3)為第二條線段的起點，p4(x4,
y4)為第二段線段的終點，由此可構(gòu)造兩個向量：

v1(x2-x1, y2-y1)，v2(x4-x3, y4-y3)
若v1與v2的外積v1×v2為0，則兩條線段平行，有可能存在部分重合。再判斷兩條平行線段是否共線，方法是用L1的一端和L2的一端構(gòu)成向量vs并與v2作外積，如果vs與v2也平行則兩線段共線（三點共線）。在共線的前提下，若起點較小的線段終點大于起點較大的線段起點，則判定為部分重合。

沒有重合，就要判定兩條線是否相交，主要的算法還是依靠外積。然而外積的計算開銷比較大，如果不相交的情況比較多，可先做快速排斥實驗：將兩條線段視為兩個矩形的對角線，并構(gòu)造出這兩個矩形。如果這兩個矩形沒有重疊部分（x坐標相離或y坐標相離）即可判定為不相交。

然后執(zhí)行跨立試驗。兩條相交的線段必然相互跨立，簡單的講就是p1和p2兩點位于L2的兩側(cè)且p3和p4兩點位于L1的兩側(cè)，這樣就可利用外積做出判斷了。分別構(gòu)造向量s1(p3,
p1), s2(p3,
p2)，如果s1×v2與s2×v2異號(s1->v2與s2->v2轉(zhuǎn)動的方向相反），則說明p1和p2位于L2的兩側(cè)。同理可判定p3和p4是否跨立L1。如果上述四個叉積中任何一個等于0，則說明一條線段的端點在另一條線上。

當判定兩條線段相交后，就可以進行交點的求解了。當然，求交點可以用平面幾何方法，列點斜式方程來完成。但這樣作會難以處理斜率為0的特殊情況，且運算中會出現(xiàn)多次除法，很難保證精度。這里將使用向量法求解。

設(shè)交點為(x0, y0)，則下列方程組必然成立：

x0-x1=k1(x2-x1) y0-y1=k1(y2-y1) x0-x3=k2(x4-x3) y0-y3=k2(y4-y3)
其中k1和k2為任意不為0的常數(shù)（若為0，則說明有重合的端點，這種情況在上面已經(jīng)被排除了）。1式與2式聯(lián)系，3式與4式聯(lián)立，消去k1和k2可得：

x0(y2-y1)-x1(y2-y1)=y0(x2-x1)-y1(x2-x1)
x0(y4-y3)-x3(y4-y3)=y0(x4-x3)-y3(x4-x3) 將含有未知數(shù)x0和y0的項移到左邊，常數(shù)項移動到右邊，得：

(y2-y1)x0+(x1-x2)y0=(y2-y1)x1+(x1-x2)y1
(y4-y3)x0+(x3-x4)y0=(y4-y3)x3+(x3-x4)y3 設(shè)兩個常數(shù)項分別為b1和b2：

b1=(y2-y1)x1+(x1-x2)y1 b2=(y4-y3)x3+(x3-x4)y3
系數(shù)行列式為D，用b1和b2替換x0的系數(shù)所得系數(shù)行列式為D1，替換y0的系數(shù)所得系數(shù)行列式為D2，則有：

|D|=(x2-x1)(y4-y3)-(x4-x3)(y2-y1) |D1|=b2(x2-x1)-b1(x4-x3)
|D2|=b2(y2-y1)-b1(y4-y3) 由此，可求得交點坐標為：

x0=|D1|/|D|, y0=|D2|/|D| 解畢。

AC代碼：

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int n,flag; int k[40]; struct node {int x,y; } s[40][110]; double f(node a,node b,node c)///如果AB.AC，得到的結(jié)果是垂直于ABC這個平面的一個向量 {///兩個向量的向量積，是一個垂直于兩個向量的向量return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);///AB.AC=（b.x-a.x）*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)； } int dfs(node a,node b,node c,node d) {if(max(a.x,b.x)>=min(c.x,d.x)&&max(c.x,d.x)>=min(a.x,b.x)&&max(a.y,b.y)>=min(c.y,d.y)&&max(c.y,d.y)>=min(a.y,b.y)&&f(a,b,c)*f(a,d,b)>=0/**(ABxAC)*(ADxAB)>=0,就是說明這 兩個向量積的方向相同，也就是姆指方向相同，也就是兩個線段相交的判 斷條件。*/&&f(a,c,d)*f(b,d,c)>=0)return 1;///如果AB和CD相交，可以畫個圖看看，ABxAC和ADxAB的拇指方向是相同的，ACxAD和BDxBC的拇指方向也是相同的。return 0; } int main() {while(~scanf("%d",&n)){memset(k,0,sizeof(k));flag=0;for(int i=0; i<n; i++){scanf("%d",&k[i]);for(int j=0; j<k[i]; j++)scanf("%d%d",&s[i][j].x,&s[i][j].y);}if(n==1){printf("No\n");continue;}for(int i=0; i<n-1; i++)///枚舉for(int j=1; j<k[i]; j++)for(int u=i+1; u<n; u++)for(int v=1; v<k[u]; v++)if(dfs(s[i][j-1],s[i][j],s[u][v-1],s[u][v])){flag=1;break;}if(flag)printf("Yes\n");elseprintf("No\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Pipe HDU - 2150(判断线段相交+向量叉乘线代详解)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。