题意:依次给出n根木棍,后放的木棍可能会覆盖前面的木棍,求没有被覆盖的木棍的序号。


题解:枚举线段相交即可,由于题目给出的数据是不可能存在1000根木棍在最上面,所以可以直接暴力枚举(但是题目没说是任何时候都没有1000根木棍在上面啊,感觉数据有点迷)。然后看别人还有用队列来做的,很神奇,就学习了一波。


代码:

StatusAccepted
Time657ms
Memory5920kB
Length2013
LangG++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const double eps=1e-8;
const int maxn=100005;
int dcmp(double x){
    if(fabs(x)<eps)return 0;return x>0?1:-1;
}
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);
    }
    double operator ^(const Point &b)const{
        return x*b.y-y*b.x;
    }
    double operator *(const Point &b)const{
        return x*b.x+y*b.y;
    }
    double distance(Point p){return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));}
};
struct Line{
    Point s, e;
    int id;
    Line(){}
    Line(Point _s, Point _e){s=_s, e=_e;}
    int segCrossSeg(Line v){
        int d1=dcmp((e-s)^(v.s-s));
        int d2=dcmp((e-s)^(v.e-s));
        int d3=dcmp((v.e-v.s)^(s-v.s));
        int d4=dcmp((v.e-v.s)^(e-v.s));
        if((d1^d2)==-2&&(d3^d4)==-2)return 2;
        return (d1==0 && dcmp((v.s-s)*(v.s-e))<=0)||(d2==0 && dcmp((v.e-s)*(v.e-e)<=0))||(d3==0 && dcmp((s-v.s)*(s-v.e))<=0)||(d4==0&&dcmp((e-v.s)*(e-v.e))<=0);
    }
};
int n;
vector<Line> line;
queue<Line> que;
void bfs(){
    que.push(line[0]);
    for(int i=1;i<line.size();i++){
        que.push(line[i]);
        while(!que.empty()){
            Line ltop=que.front();que.pop();
            if(ltop.id==line[i].id){
                que.push(ltop);break;
            }
            if(line[i].segCrossSeg(ltop)!=2)que.push(ltop);
        }
    }
}
int main()
{
    while(~scanf("%d", &n)&&n){
        line.clear();
        for(int i=0;i<n;i++){
            Line l1;l1.id=i+1;
            scanf("%lf%lf%lf%lf", &l1.s.x,&l1.s.y,&l1.e.x,&l1.e.y);
            line.push_back(l1);
        }
        bfs();
        printf("Top sticks:");
        while(!que.empty()){
            Line l1=que.front();
            que.pop();
            printf(" %d%c", l1.id, que.size()==0?'.':',');
        }
        puts("");
    }
    return 0;
}