poj 2653 线段相交裸题（解题报告）

ゝ一世哀愁。 2021-11-01 13:16 280阅读 0赞

#include<stdio.h>
    #include<math.h>
    
    const double eps=1e-8;
    int n;
    int cmp(double x)
    {
    
        if(fabs(x)<=eps)return 0;
        if(x<0)return -1;
        return 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.x+y*b.y;
        }
        double operator ^(const Point &b)const{
        return x*b.y-b.x*y;
        }
    };
    
    struct Line
    {
        Point s,e;
        Line (){}
        Line (Point  _s,Point _e)
        {
            s=_s;
            e=_e;
        }
    };
    
    Line line [(int)1e5+5];
    double xmult(Point p0,Point p1,Point  p2)
    {
        return (p1-p0)^(p2-p0);
    }
    
    bool seg_seg(Line l1,Line l2)
    {
        return cmp(xmult(l1.s,l2.s,l2.e))*cmp(xmult(l1.e,l2.s,l2.e))<=0&&cmp(xmult(l2.e,l1.s,l1.e))*cmp(xmult(l2.s,l1.s,l1.e))<=0;
    }
    
    bool check(int num)
    {
        for(int j=num+1;j<n;j++)
        {
            if(seg_seg(line[num],line[j])==true)
                return false;
        }
        return true;
    }
    
    int a[1005];
    int main()
    {
        double x1,x2,y1,y2;
        while(scanf("%d",&n),n)
        {
            int t=0;
            for(int i=0;i<n;i++)
            {
                scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
                line[i]=Line(Point(x1,y1),Point(x2,y2));
            }
            for(int i=0;i<n;i++)
                if(check(i))
                a[t++]=i;
            printf("Top sticks: ");
            for(int i=0;i<t;i++)
            {
                printf("%d",a[i]+1);
                if(i<t-1)
                    printf(", ");
    
            }
            printf(".\n");
        }
    }

思路：TOP STICK ：压在最上边的木棍，从最先放的木棍开始遍历，如果在其后边的木棍不压在它身上，即其后的木棍不与其相交（线段相交），则这个木棍就是top stick

转载于:https://www.cnblogs.com/zwx7616/p/11200511.html