题意解释：

    给出几根棍子扔出的顺序，抛出方式任意，有的会重叠有的不会，问最后哪些棍子不被其他的棍子压住。

选题原因：

计算几何中判断直线的相交是一个热门问题，通过此题向大家介绍判断直线相交的几种基本方法。几何问题的解决离不开图，所以建议大家在面对几何问题时多借助做图来理解题意。

1.判断两条直线相交

    先来看一个简单的情况，即判断两条直线是否相交。

第一个可能会想到的办法，就是判断斜率，这个在中学时代就学过了，不过斜率需要考虑垂直的特殊情况，比较麻烦。更好的办法或许是计算两个向量的叉积，如果为0，则是平行或者重合的，否则两直线相交。

2判断两线段相交

经典方法，就是跨立试验了，即如果一条线段跨过另一条线段，则线段的两个端点分别在另一条线段的两侧。但是，还需要检测边界情况，即两条线段中可能某条线段的某个端点正好落在另一条线段上。这也是算法导论中介绍的算法。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int N=100001;

const double eps=1e-10;

struct node

{

    double x,y;

}p[N],b[N];

bool ans[N];

double min(double a,double b) {return a<b?a:b;}

double max(double a,double b) {return a>b?a:b;}

bool judge(node p1,node p2,node p3,node p4)

{

    if(min(p1.x,p2.x)>max(p3.x,p4.x)||//这个判断是快速排斥实验

       min(p1.y,p2.y)>max(p3.y,p4.y)||

       min(p3.x,p4.x)>max(p1.x,p2.x)||

       min(p3.y,p4.y)>max(p1.y,p2.y))

       return 0;

       double a,b,c,d;//以下是跨立实验，原则是

       a=(p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);

       b=(p2.x-p1.x)*(p4.y-p1.y)-(p2.y-p1.y)*(p4.x-p1.x);

       c=(p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x);

       d=(p4.x-p3.x)*(p2.y-p3.y)-(p4.y-p3.y)*(p2.x-p3.x);

 //前面已经经过排斥实验，所以不用担心上图4的情况

       return a*b<=eps&&c*d<=eps;

}

int main()

{

    int n;

    int res[N];

    while(scanf("%d",&n)!=EOF&&n)

    {

        memset(ans,0,sizeof(ans));

        for(int i=0;i<n;i++)

        {

            scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&b[i].x,&b[i].y);

     }

        for(int i=0;i<n;i++)

        {

            for(int j=i+1;j<n;j++)

            {

                if(judge(p[i],b[i],p[j],b[j]))

                {

                    ans[i]=1;

                    break;

                }

            }

        }

        int cc=0;

        printf("Top sticks:");

        for(int i=0;i<n;i++)

        {

            if(!ans[i]) res[cc++]=i+1;

        }

        for(int i=0;i<cc-1;i++)

        printf(" %d,",res[i]);

        printf(" %d.\n",res[cc-1]);

    }

    return 0;

}

geometry2653