题意:依次给出n根木棍,后放的木棍可能会覆盖前面的木棍,求没有被覆盖的木棍的序号。
题解:枚举线段相交即可,由于题目给出的数据是不可能存在1000根木棍在最上面,所以可以直接暴力枚举(但是题目没说是任何时候都没有1000根木棍在上面啊,感觉数据有点迷)。然后看别人还有用队列来做的,很神奇,就学习了一波。
代码:
Status | Accepted |
---|---|
Time | 657ms |
Memory | 5920kB |
Length | 2013 |
Lang | G++ |
#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; }