1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <algorithm> 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<l){59             int i=que[f++];60             if(!flag){61                      printf(" %d",i);62                      flag=true;63             }64             else{65                     printf(", %d",i);66             }67         }68         printf(".\n");69     }70     return 0;71 }