hdu1147(Pick-up sticks)

hdu1147(Pick-up sticks)

題目意思：

但順序給出n個小木棍(線段)，取走在最頂上的木棍。

題目分析：

仔細想想此題還是判斷線段是否相交，只是需要注意順序，只能判斷每個線段(木棍)後面放的木棍。類似於hdu1108。

AC代碼：

/**
*判斷後面的線段是否與前面的線段相交,
*此題還是一個判斷線段是否相交的問題,
*只是必須注意順序,判斷相交的函數減hdu1086
*/
#include
#include
#include
using namespace std;
typedef struct Node{
double x,y;
}node;
node p[100005],p1[100005];
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){//判斷兩條線段是否相交,相交返回true
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;//輸入第一個點
cin>>p1[i].x>>p1[i].y;//輸入第二個點
}
cout< for(int i=1;i int ok=1;
for(int j=i+1;j<=n;j++){//之判斷在該線段之後拋下的線段(木棍)
if(Segments_X(p[i],p1[i],p[j],p1[j])){
ok=0; break;
}
}
if(ok) cout< }
cout<
}
return 0;
}