POJ 2653 Pick-up sticks

计算几何，判断线段相交

注意题目中的一句话：You may assume that there are no more than 1000 top sticks.

我认为是没有描述清楚的，如果不是每次扔完都保证不超过1000，此题很难做吧。

如果每次扔完保证小于1000根在顶部，那么暴力即可。

开一个vector保存每次扔完在顶部的棒子，下一次扔的时候，只要在删除vector中与扔的相交的棒子，然后再把这个棒子压入进来，最后留下的就是答案

#include<cstdio>

#include<cstring>

#include<vector>

#include<cmath>

#include<queue>

#include<list>

#include<algorithm>

using namespace std;

const int maxn=+;

const double eps=1e-;

int totP,totL;

struct point

{

    double x;

    double y;

} p[*maxn];

struct Line

{

    point a;

    point b;

    int id;

} line[maxn];

vector<Line> v;

vector <Line>::iterator Iter;

vector<int> ans;

int flag[maxn];

double xmult(point p1,point p2,point p0)

{

    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

}

int opposite_side(point p1,point p2,point l1,point l2)

{

    return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps;

}

int intersect_ex(point u1,point u2,point v1,point v2)

{

    return opposite_side(u1,u2,v1,v2)&&opposite_side(v1,v2,u1,u2);

}

int main()

{

    while(~scanf("%d",&totL))

    {

        if(!totL) break;

        totP=;

        for(int i=; i<totL; i++)

        {

            double a,b,c,d;

            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);

            p[totP+].x=a;

            p[totP+].y=b;

            p[totP+].x=c;

            p[totP+].y=d;

            line[i].a=p[totP+];

            line[i].b=p[totP+];

            line[i].id=i;

            totP=totP+;

        }

        v.clear();

        for(int i=; i<totL; i++)

        {

            for (Iter=v.begin();Iter!=v.end();)

            {

                Line now=*Iter;

                if(intersect_ex(line[i].a,line[i].b,now.a,now.b))

                    Iter = v.erase(Iter);

                else Iter++;

            }

            v.push_back(line[i]);

        }

        ans.clear();

        for (Iter=v.begin();Iter!=v.end();Iter++ )

        {

            Line now=*Iter;

            ans.push_back(now.id);

        }

        printf("Top sticks: ");

        for(int i=; i<ans.size(); i++)

        {

            printf("%d",ans[i]+);

            if(i<ans.size()-) printf(", ");

            else printf(".\n");

        }

    }

    return ;

}