开一个数组做成队列来搜索就好了。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int MAXN=100010; 9 10 typedef struct po{11 double x,y;12 }Point;13 struct e{14 Point start,end;15 }edge[MAXN],ss,ee;16 int n;17 double x1,y1,x2,y2;18 Point start,end;19 int que[MAXN*100];20 21 double multi(Point p1, Point p2, Point p0){22 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);23 }24 25 bool slove(int k,int i){26 ss=edge[k]; ee=edge[i];27 if(max(ss.start.x,ss.end.x)>=min(ee.start.x,ee.end.x)&&28 max(ee.start.x,ee.end.x)>=min(ss.start.x,ss.end.x)&&29 max(ss.start.y,ss.end.y)>=min(ee.start.y,ee.end.y)&&30 multi(ee.start,ss.end,ss.start)*multi(ss.end,ee.end,ss.start)>0&&31 multi(ss.start,ee.end,ee.start)*multi(ee.end,ss.end,ee.start)>0){32 return true;33 }34 return false; 35 }36 37 int main(){38 int f,l;39 while(scanf("%d",&n)!=EOF){40 if(n==0) break; f=l=0;41 for(int i=1;i<=n;i++){42 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);43 start.x=x1; start.y=y1;44 end.x=x2; end.y=y2;45 edge[i].start=start; edge[i].end=end;46 if(i>1){47 int size=l-f;48 while(size--){49 int k=que[f++];50 if(!slove(k,i))51 que[l++]=k;52 }53 }54 que[l++]=i;55 }56 bool flag=false;57 printf("Top sticks:");58 while(f