POJ 1269 Intersecting Lines(直线相交判断求交点)

系统管理员 2022-05-18 06:07 183阅读 0赞

[题目链接][Link 1]

题目大意：每次给你两条线段，判断它们的位置关系，如果相交，还需输出它们的交点。

分析：线段之间存在三种关系，平行，共线，相交。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #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 = 1e2+7;
    const double eps = 1e-8;
    
    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;}
    };
    
    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-a.y*b.x;
    }
    
    int parallel(Line l1,Line l2)
    {
        return ((l1.e.x-l1.s.x)*(l2.e.y-l2.s.y)-(l1.e.y-l1.s.y)*(l2.e.x-l2.s.x));
    }
    
    /*Point intersection(Line l1,Line l2)
    {
        Point ret=l1.s;
        double t=((l1.s.x-l2.s.x)*(l2.s.y-l2.e.y)-(l1.s.y-l2.s.y)*(l2.s.x-l2.e.x))/((l1.s.x-l1.e.x)*(l2.s.y-l2.e.y)-(l1.s.y-l1.e.y)*(l2.s.x-l2.e.x));
        ret.x+=(l1.e.x-l1.s.x)*t;
        ret.y+=(l1.e.y-l1.s.y)*t;
        return ret;
    }*/
    
    Point intersection(Line l1,Line l2)
    {
        Point ret;
        double a1=l1.s.y-l1.e.y,b1=l1.e.x-l1.s.x,c1=l1.s.x*l1.e.y-l1.e.x*l1.s.y;
        double a2=l2.s.y-l2.e.y,b2=l2.e.x-l2.s.x,c2=l2.s.x*l2.e.y-l2.e.x*l2.s.y;
        double x1 = (c1*b2-c2*b1)/(a2*b1-a1*b2);
        double y1 = (a2*c1-a1*c2)/(a1*b2-a2*b1);
        ret.x=x1;ret.y=y1;
        return ret;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        double x1,y1,x2,y2,x3,y3,x4,y4;
        printf("INTERSECTING LINES OUTPUT\n");
        while(T--)
        {
            Line l1,l2;
            scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&l1.s.x,&l1.s.y,&l1.e.x,&l1.e.y,&l2.s.x,&l2.s.y,&l2.e.x,&l2.e.y);
            if(fabs(parallel(l1,l2))<=eps)
            {
                if(fabs(cross(l1.s,l1.e,l2.s))<=eps)
                {
                    printf("LINE\n");
                }
                else printf("NONE\n");
            }
            else{
                Point t = intersection(l1,l2);
                printf("POINT %.2f %.2f\n",t.x,t.y);
            }
        }
        printf("END OF OUTPUT\n");
        return 0;
    }

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