POJ2653 Pick-up sticks（线段相交判断）

题意是一堆木条从天而降，要找到哪些木条是在最上面的。

很简单的一道题，就是直接for循环判断会超时，这里运用了队列的思想。
这里写图片描述

附上代码：

#include <iostream>
#include <cstdio>
using namespace std;

#define eps 1e-8;

struct point{
    double x;
    double y;
};

struct line{
    int id;
    point a;
    point b;
    int prev,next;
}l[100050];

int num;

double xmult (point p0 ,point p1 ,point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
//判两点在线段异侧,点在线段上返回0
bool opposite_side (point p1 ,point p2 ,line l){
    return xmult(l.a,l.b,p1)*xmult(l.a,l.b,p2)<-eps;
}
//判两线段相交,不包括端点和部分重合
bool intersect_ex(line u, line v){
    return opposite_side(u.a,u.b,v)&&opposite_side(v.a,v.b,u);
}
int main()
{
    int n;
    while(cin>>n&&n){
        num=0;
        for (int i=1 ;i<=n ;i++){
            cin>>l[i].a.x>>l[i].a.y>>l[i].b.x>>l[i].b.y;
            l[i].id=1;l[i].next=0;l[i].prev=num;l[num].next=i;
            for(int j=num;j;j=l[j].prev)
                 if(intersect_ex(l[i],l[j]))
                 {
                     l[j].id=false;
                     l[l[j].prev].next=l[j].next;
                     l[l[j].next].prev=l[j].prev;
                 }
             num=i;
        }
        printf("Top sticks:");
        for(int i=1;i<n;i++)
             if(l[i].id)printf(" %d,",i);
         printf(" %d.
",n);
    }
}