hdu1086(線段相交)

hdu1086(線段相交)

題目意思：

給出n個線段，判斷這n條線段中，線段相交的對數。

 

題目分析：

此題主要寫出判斷線段相交的函數，然後判斷每一對線段即可，時間復雜度O(n*n)。詳細解釋見代碼。

 

AC代碼：

 

/**
*判斷AB和CD兩線段是否有交點：
*同時滿足兩個條件：('x'表示叉積)
*　1．C點D點分別在AB的兩側．(向量(ABxAC)*(ABxAD)<=0)
*　2．A點和B點分別在CD兩側．(向量(CDxCA)*(CDxCB)<=0)
* 3. 向量(ABxAC)*(ABxAD)<0代表在直線兩側, =0代表在直線上。
*/
#include
#include
#include
#include
#include
using namespace std;
typedef struct Node{
double x,y;
}node;
node p[105],p1[101];
double Direction(node pi,node pj,node pk){//計算叉乘
return (pk.x-pi.x)*(pj.y-pi.y)-(pj.x-pi.x)*(pk.y-pi.y);
}

bool Segments_X(node p1,node p2,node p3,node p4){//判斷兩條線段是否相交
double d1,d2,d3,d4;
d1=Direction(p3,p4,p1);
d2=Direction(p3,p4,p2);
d3=Direction(p1,p2,p3);
d4=Direction(p1,p2,p4);
if(d1*d2<=0&&d3*d4<=0) return true;
return false;
}
int main()
{
int n;
while(cin>>n&&n){
for(int i=1;i<=n;i++){
cin>>p[i].x>>p[i].y>>p1[i].x>>p1[i].y;
}
int k=0;
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
if(Segments_X(p[i],p1[i],p[j],p1[j])) k++;
}
}
cout< }
return 0;
}