学步园

题意：按顺序给一系列的线段，问最终哪些线段处在顶端。

思路：暴力枚举，数据量比较大，从第一根向后枚举，如果相交立刻跳出。我的程序500ms，如果把求交点的部分省略掉应该能更快

#include <cmath>
#include <cstdio>
#include <cstring>

const int N=100005;

struct Point  //点,向量
{
	double x,y;
	Point(){}
	Point(double _x,double _y)
	{x=_x;y=_y;}
	Point operator-(const Point &b)const
	{return Point(x-b.x,y-b.y);}

    Point operator+(const Point &b)
	{return Point(x+b.x,y+b.y);}

    Point operator*(const double k)  //数乘
    {return Point(x*k,y*k);}

	double operator*(const Point a)  //点乘
    {return x*a.x+y*a.y;}

    double operator^(const Point a)  //叉乘
    {return x*a.y-y*a.x;}
    //调用点a的该函数
    //返回正值点a在向量bc的左侧
    //返回负值点a在向量bc的右侧
    //返回0点a在向量bc这条直线上
    double Cross (Point b,Point c)
    {return (b.x-x)*(c.y-y)-(c.x-x)*(b.y-y);}
};

int DB (double x)
{
	if(fabs(x)<1e-6) return 0;
	return x>0?1:-1;
}

int betweenCmp(Point a,Point b,Point c)
{
	return DB(a.Cross(b,c));
}

//参数：两线段两端点：a、b和c、d和用于保存交点的ans。
//返回：0：不相交
//      1：规范相交，答案保存在ans中
//      2：非规范相交 答案保存在ans中
int Segcross (Point a,Point b,Point c,Point d,Point &ans)
{
	double s1,s2,s3,s4;
	int d1,d2,d3,d4;

	d1=DB(s1=a.Cross(b,c));
	d2=DB(s2=a.Cross(b,d));
	d3=DB(s3=c.Cross(d,a));
	d4=DB(s4=c.Cross(d,b));

	if((d1^d2)==-2 && (d3^d4)==-2)
	{
		ans.x=(c.x*s2-d.x*s1)/(s2-s1);
		ans.y=(c.y*s2-d.y*s1)/(s2-s1);
		return 1;
	}

	if(d1==0&&betweenCmp(c,a,b)<=0) {ans=c;return 2;}
	if(d2==0&&betweenCmp(d,a,b)<=0) {ans=d;return 2;}
	if(d3==0&&betweenCmp(a,c,d)<=0) {ans=a;return 2;}
	if(d4==0&&betweenCmp(b,c,d)<=0) {ans=b;return 2;}
	return 0;
}
Point up[N],down[N];
int ans[N];

int main ()
{
#ifdef ONLINE_JUDGE
#else
	freopen("read.txt","r",stdin);
#endif
    int n;
	while (scanf("%d",&n),n)
	{
	    int i,j,cnt=0;
	    memset(ans,0,sizeof(ans));
	    for (i=1;i<=n;i++)
            scanf("%lf%lf%lf%lf",&up[i].x,&up[i].y,&down[i].x,&down[i].y);
        Point temp;
        for (i=1;i<n;i++)
        {
            bool flag=true;
            for (j=i+1;j<=n;j++)
                if (Segcross(up[i],down[i],up[j],down[j],temp))
                {
                    flag=false;
                    break;
                }
            if (flag) ans[cnt++]=i;
        }
        ans[cnt]=n;  //最后一根肯定在最上面
        printf("Top sticks: ");
        for (i=0;i<=cnt;i++)
            printf(i==cnt?"%d.\n":"%d, ",ans[i]);
	}
	return 0;
}