POJ2653 Pick-up sticks

原题传送门：http://poj.org/problem?id=2653
博主的中文题面（数据范围较小）：
https://www.luogu.org/problemnew/show/T22901

Pick-up sticks

Description

Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.

Input

Input consists of a number of cases. The data for each case start with 1 <= n <= 100000, the number of sticks for this case. The following n lines contain four numbers each, these numbers are the planar coordinates of the endpoints of one stick. The sticks are listed in the order in which Stan has thrown them. You may assume that there are no more than 1000 top sticks. The input is ended by the case with n=0. This case should not be processed.

Output

For each input case, print one line of output listing the top sticks in the format given in the sample. The top sticks should be listed in order in which they were thrown.

The picture to the right below illustrates the first case from input.

Sample Input

5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
3
0 0 1 1
1 0 2 1
2 0 3 1
0

Sample Output

Top sticks: 2, 4, 5.
Top sticks: 1, 2, 3.

Hint

Huge input,scanf is recommended.

题目大意

按顺序给出多条线段，后面的线段可覆盖前面的，求在最上面的线段。

题解

这道题数据比较水（因为题目保证在顶端的棍子不超过1000，然而中间结果是可能超过一千的，不过数据很水没有卡），博主O(nm)的算法居然A了。  
只需要按棍子抛出的顺序枚举，将当前在顶端的线段储存在数组中，每次加入新线段时爆扫一遍，如果该线段被新的线段覆盖，就将该线段弹出，（腾出的空间可以装新的线段，扫描的时候记一下就好了，不加这个优化会T。当然，你也可以加链表）没有可覆盖的线段的话就放在队位，枚举完排一边序即可AC（输出格式稍微注意一下）。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define db double
using namespace std;
const int M=1e5+10;
const db eps=1e-8;
int n,top,tot;
struct pt{db x,y;};
struct li{pt x1,x2;int n;};
bool operator < (const li &a,const li &b){return a.n<b.n;}
li line[M];
li ans[M];
void in()
{
    pt a,b;
    for(int i=1;i<=n;++i)
    {
        scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
        line[i].x1=a;line[i].x2=b;line[i].n=i;
    }
}
int sig(db x){return (x>eps)-(x<-eps);}
db operator * (pt a,pt b){return a.x*b.y-a.y*b.x;}
pt operator - (pt a,pt b){pt hh;hh.x=a.x-b.x;hh.y=a.y-b.y;return hh;}
db cross(pt a,pt b,pt c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool test(li x,li y)
{
    int s1,s2,s3,s4;
    s1=sig(cross(x.x1,y.x1,y.x2));
    s2=sig(cross(x.x2,y.x1,y.x2));
    s3=sig(cross(y.x1,x.x1,x.x2));
    s4=sig(cross(y.x2,x.x1,x.x2));
    if((s1^s2)==-2&&(s3^s4)==-2) return 0;
    return 1;
}
void check(li x)
{
    int pos=-1;
    for(int i=1;i<=top;++i)
    {
        if(ans[i].n>=1e9)
        {
            pos=i;
            continue;
        }
        if(!test(x,ans[i]))
        {
            --tot;
            ans[i].n=1e9;
        }
    }
    ++tot;
    if(pos>0) ans[pos]=x;
    else ans[++top]=x;
}
void ac()
{
    top=0;
    tot=1;
    ans[++top]=line[1];
    for(int i=2;i<=n;++i)
    check(line[i]);
    sort(ans+1,ans+1+top);
    printf("Top sticks: ");
    for(int i=1;i<tot;++i)
    printf("%d, ",ans[i].n);
    printf("%d.\n",ans[tot].n);
    memset(ans,0,sizeof(ans));
    memset(line,0,sizeof(line));
}
int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        in(),ac();
    }
    return 0;
}