1    #include <cmath>  2    #include <cstdio>  3    #include <iostream>  4    #include <cstring>  5    using namespace std;  6   7    #define eps 1e-8  8    #define PI acos(-1.0)//3.14159265358979323846  9    //判断一个数是否为0,是则返回true,否则返回false 10    #define zero(x)(((x)>0?(x):-(x))<eps) 11    //返回一个数的符号，正数返回1，负数返回2，否则返回0 12    #define _sign(x)((x)>eps?1:((x)<-eps?2:0)) 13  14   struct point 15   { 16       double x,y; 17       point(){} 18       point(double xx,double yy):x(xx),y(yy) 19       {} 20   }; 21   struct line 22   { 23       point a,b; 24       line(){}      //默认构造函数 25       line(point ax,point bx):a(ax),b(bx) 26       {} 27   };//直线通过的两个点，而不是一般式的三个系数 28  29     int n; 30     double ax1,ay1,ax2,ay2,bx1,by1,bx2,by2; 31  32    //求矢量[p0,p1],[p0,p2]的叉积 33    //p0是顶点 34    //若结果等于0，则这三点共线 35    //若结果大于0，则p0p2在p0p1的逆时针方向 36    //若结果小于0，则p0p2在p0p1的顺时针方向 37    double xmult(point p1,point p2,point p0) 38    { 39        return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 40    } 41    //计算dotproduct(P1-P0).(P2-P0) 42    double dmult(point p1,point p2,point p0) 43    { 44        return(p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y); 45    } 46    //两点距离 47    double distance(point p1,point p2) 48    { 49        return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); 50    } 51    //判三点共线 52    int dots_inline(point p1,point p2,point p3) 53    { 54        return zero(xmult(p1,p2,p3)); 55    } 56    //判点是否在线段上,包括端点 57    int dot_online_in(point p,line l) 58    { 59        return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps; 60    } 61    //判点是否在线段上,不包括端点 62    int dot_online_ex(point p,line l) 63    { 64        return dot_online_in(p,l)&&(!zero(p.x-l.a.x)||!zero(p.y-l.a.y))&&(!zero(p.x-l.b.x)||!zero(p.y-l.b.y)); 65    } 66    //判两点在线段同侧,点在线段上返回0 67    int same_side(point p1,point p2,line l) 68    { 69        return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps; 70    } 71    //判两点在线段异侧,点在线段上返回0 72    int opposite_side(point p1,point p2,line l) 73    { 74        return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)<-eps; 75    } 76    //判两直线平行 77    int parallel(line u,line v) 78    { 79        return zero((u.a.x-u.b.x)*(v.a.y-v.b.y)-(v.a.x-v.b.x)*(u.a.y-u.b.y)); 80    } 81    //判两直线垂直 82    int perpendicular(line u,line v) 83    { 84        return zero((u.a.x-u.b.x)*(v.a.x-v.b.x)+(u.a.y-u.b.y)*(v.a.y-v.b.y)); 85    } 86    //判两线段相交,包括端点和部分重合 87    int intersect_in(line u,line v) 88    { 89        if(!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b)) 90            return!same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u); 91        return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u); 92    } 93    //判两线段相交,不包括端点和部分重合 94    int intersect_ex(line u,line v) 95    { 96        return opposite_side(u.a,u.b,v)&&opposite_side(v.a,v.b,u); 97    } 98    //计算两直线交点,注意事先判断直线是否平行! 99    //线段交点请另外判线段相交(同时还是要判断是否平行!)100    point intersection(line u,line v)101    {102        point ret=u.a;103        double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));104        ret.x+=(u.b.x-u.a.x)*t;105        ret.y+=(u.b.y-u.a.y)*t;106        return ret;107    }108 109   int main()110   {111       cin>>n;112       cout<<"INTERSECTING LINES OUTPUT"<<endl;113       for (int i=1;i<=n;i++)114       {115         cin>>ax1>>ay1>>ax2>>ay2>>bx1>>by1>>bx2>>by2;116         point a1(ax1,ay1);  point a2(ax2,ay2);117         point b1(bx1,by1);  point b2(bx2,by2);118         line l1=line(point(ax1,ay1),point(ax2,ay2));119         line l2=line(point(bx1,by1),point(bx2,by2));120         if ((dots_inline(a1,a2,b1)>0)&&(dots_inline(a1,a2,b2)>0))121             cout<<"LINE";122         else if (parallel(l1,l2)>0)     cout<<"NONE";123         else124         {125             point tm=intersection(l1,l2);126             cout<<"POINT ";127             printf("%.2f %.2f",tm.x,tm.y);128         }129         cout<<endl;130       }131       cout<<"END OF OUTPUT"<<endl;132       return 0;133   }