POJ 2653 Pick-up sticks(线段相交)

Love The Way You Lie 2022-05-18 06:08 181阅读 0赞

[题目链接][Link 1]

题目大意：有n根木条（1 <= n <= 100000），一根一根的往一个坐标系上丢，问最后不被覆盖的木条有哪些，即丢的木条如果和前面丢的木条交叉的话，就会覆盖前面那根木条。

分析：因为丢出的木条是按顺序给出的，因为在上方的木条不超过1000根，所以直接枚举每条线段，如果他后面有和他相交的线段，那么这条线段就会被覆盖，标记一下，最后输出没被标记的就行了。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include <iomanip>
    #include<utility>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn = 1e5+7;
    const double eps = 1e-8;
    int n;
    
    int sgn(double x)
    {
        if(fabs(x)<eps) return 0;
        else return x<0?-1:1;
    }
    
    struct Point{
        double x,y;
        Point(){}
        Point(double _x,double _y){x=_x;y=_y;}
    };
    
    struct Line{
        Point s,e;
        Line(){}
        Line(Point _s,Point _e){s=_s;e=_e;}
    }line[maxn];
    
    int vis[maxn];
    
    double cross(Point a,Point b,Point c)
    {
        a.x-=c.x;a.y-=c.y;
        b.x-=c.x;b.y-=c.y;
        return a.x*b.y-b.x*a.y;
    }
    
    bool intersect(Line l1,Line l2){
        return(sgn(max(l1.s.x,l1.e.x)-min(l2.s.x,l2.e.x))>=0&&         //排斥实验
                sgn(max(l2.s.x,l2.e.x)-min(l1.s.x,l1.e.x))>=0&&
                sgn(max(l1.s.y,l1.e.y)-min(l2.s.y,l2.e.y))>=0&&
                sgn(max(l2.s.y,l2.e.y)-min(l1.s.y,l1.e.y))>=0&&
                sgn(cross(l2.s,l1.e,l1.s)*cross(l2.e,l1.e,l1.s)<=0)&& //跨立实验
                sgn(cross(l1.s,l2.e,l2.s)*cross(l1.e,l2.e,l2.s)<=0));
    }
    
    int main()
    {
        int n;
        while(scanf("%d",&n)==1&&n)
        {
            Clear(vis);
            double x1,y1,x2,y2;
            for(int i=1;i<=n;i++)
            {
                scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
                line[i]=Line(Point(x1,y1),Point(x2,y2));
                vis[i]=1;
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=i+1;j<=n;j++)
                {
                    if(intersect(line[i],line[j]))
                    {
                        vis[i]=0;
                        break;
                    }
                }
            }
            int first = 1;
            printf("Top sticks: ");
            for(int i=1;i<=n;i++)
            {
                if(vis[i])
                {
                    if(first) first=0;
                    else printf(", ");
                    printf("%d",i);
                }
            }
            printf(".\n");
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=2653