1   #include<math.h>  2   #include <stdio.h>  3   #include <string.h>  4   5   bool ans[100100];  6   int n;  7   double X1,X2,Y1,Y2;  8   9   #define eps 1e-8 10   #define PI acos(-1.0)//3.14159265358979323846 11   //判断一个数是否为0,是则返回true,否则返回false 12   #define zero(x)(((x)>0?(x):-(x))<eps) 13   //返回一个数的符号，正数返回1，负数返回2，否则返回0 14   #define _sign(x)((x)>eps?1:((x)<-eps?2:0)) 15  16   struct point 17   { 18       double x,y; 19       point(){} 20       point(double xx,double yy):x(xx),y(yy) 21       {} 22   }; 23  24   struct line 25   { 26       point a,b; 27       line(){}      //默认构造函数 28       line(point ax,point bx):a(ax),b(bx) 29       {} 30   }l[100100]; 31  32   //求矢量[p0,p1],[p0,p2]的叉积  //p0是顶点 33   //若结果等于0，则这三点共线  //若结果大于0，则p0p2在p0p1的逆时针方向  //若结果小于0，则p0p2在p0p1的顺时针方向 34   double xmult(point p1,point p2,point p0) 35   { 36       return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 37   } 38   //计算dotproduct(P1-P0).(P2-P0) 39   double dmult(point p1,point p2,point p0) 40   { 41       return(p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y); 42   } 43   //两点距离 44   double distance(point p1,point p2) 45   { 46       return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); 47   } 48   //判三点共线 49   int dots_inline(point p1,point p2,point p3) 50   { 51       return zero(xmult(p1,p2,p3)); 52   } 53   //判点是否在线段上,包括端点 54   int dot_online_in(point p,line l) 55   { 56       return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps; 57   } 58   //判点是否在线段上,不包括端点 59   int dot_online_ex(point p,line l) 60   { 61       return dot_online_in(p,l)&&(!zero(p.x-l.a.x)||!zero(p.y-l.a.y))&&(!zero(p.x-l.b.x)||!zero(p.y-l.b.y)); 62   } 63   //判两点在线段同侧,点在线段上返回0 64   int same_side(point p1,point p2,line l) 65   { 66       return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps; 67   } 68     //判两线段相交,包括端点和部分重合 69   int intersect_in(line u,line v) 70   { 71       if(!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b)) 72           return!same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u); 73       return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u); 74   } 75  76 int main() 77 { 78     while (scanf("%d",&n)) 79     { 80     if (n==0)   break; 81     memset(ans,false,sizeof(ans)); 82     for (int i=1;i<=n;i++) 83     { 84         //cin>>X1>>Y1>>X2>>Y2; 85         scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2); 86         l[i]=line(point(X1,Y1),point(X2,Y2)); 87         ans[i]=true; 88     } 89  90     for (int i=1;i<=n-1;i++) 91     { 92         int j=i+1; 93         while (j<=n) 94         { 95             line l1=l[i],l2=l[j]; 96             if (intersect_in(l1,l2)!=0) 97             { 98                 ans[i]=false; 99                 break;100             }101             j++;102         }103     }104     //Top sticks: 2, 4, 5.105     int ANS[1010];106     int nm=0;107     for (int i=1;i<=n;i++)108         if (ans[i])109         {110             nm++;111             ANS[nm]=i;112         }113     printf("Top sticks: ");114     for (int i=1;i<nm;i++)115         printf("%d, ",ANS[i]);116     printf("%d.\n",ANS[nm]);117     }118     return 0;119 }