判断两条直线共线或平行或相交求交点叉乘的应用 poj 1269 Intersecting Lines...-白红宇

判断两条直线共线或平行或相交求交点叉乘的应用 poj 1269 Intersecting Lines...

阅读量：5964 次

发布时间：2019-06-19

本文共 3822 字，大约阅读时间需要 12 分钟。

题目来源：http://poj.org/problem?id=1269

分析：

题目大意：给两个点能够确定一条直线，题目给出两条直线（由4个点确定），要求判断出这两条直线的关系：平行，同线，相交。如果相交还要求出交点坐标。

解题思路：

先判断两条直线p1p2, q1q2是否共线，如果不是，再判断直线是否平行，如果还不是，则两直线相交。

判断共线： p1p2q1 共线且 p1p2q2 共线，共线用叉乘为 0 来判断，

判断平行： p1p2 与 q1q2 共线

求交点：

直线p1p2上的点可表示为 p1+t(p2-p1) ，而交点又在直线q1q2上，所以有（q2-q1）X (p1 + t(p2-p1 ) - q1 ) =0

解得交点 t = p1 + ( ((q2-q1) X (q1 - p1)) /( (q2-q1) X(p2-p1) ) *(p2-p1) )

注意： double 型数据为0 不能直接==0

较简洁的代码：

double add(double a, double b){    return (fabs(a + b) < EPS * (fabs(a) + fabs(b))) ? 0 : (a + b) ;}struct Point{    double x, y;    Point(){}    Point(double x, double y):x(x),y(y){}    Point operator - (Point a){        return Point( add(x , -a.x), add(y , -a.y)) ;    }    Point operator + (Point a){        return Point( add(x , a.x), add(y , a.y)) ;    }    double  operator ^(Point a){        return add(x * a.y , -y * a.x) ;    }    Point  operator * (double d){        return Point(x * d ,y * d) ;    }};bool on_segment(Point p1, Point p2, Point p){    return ((p1 - p).x * (p2 - p).x <= 0 )&&((p1 - p).y * (p2 - p).y <= 0) ;}struct Line{    Point st , ed ;    Line(){}    Line(Point s, Point e){        st = s ;        ed = e ;    }    bool parallel(Line l){        return ((ed - st)^(l.ed - l.st)) == 0 ;    }    bool overlap(Line l){        return (((ed - st)^(l.ed - st)) == 0 ) && (((ed -st)^(l.ed - st)) == 0) ;    }    Point intersectionode(Line l){        double t = (l.ed - l.st)^(l.st - st) ;        double t1 = (l.ed - l.st)^(ed - st) ;        return st + (ed - st) * (t / t1) ;    }    void read(){        scanf("%lf%lf%lf%lf" , &st.x, &st.y ,&ed.x ,&ed.y);    }};Line l1 ,l2;int main(){    int t ;    scanf("%d" , &t) ;    printf("INTERSECTING LINES OUTPUT\n") ;    while(t--){        l1.read() ;        l2.read() ;        if(l1.parallel(l2)){            if((((l2.ed -l2.st)^(l1.ed - l2.st)) == 0))                puts("LINE") ;  //先判断共线            else puts("NONE") ;//再判断平行        }        else {        Point ix = l1.intersectionode(l2) ; //最后 直线相交        printf("POINT %.2lf %.2lf\n" , ix.x ,ix.y) ;         }    }    puts("END OF OUTPUT") ;   return 0 ;}

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include
            using namespace std;typedef long long ll;const int N =30;const double PI = 3.1415927;const double EPS=1e-10;struct Point{ double x,y; Point(){} Point(double x,double y):x(x),y(y){} // 构造函数，方便代码编写 Point(const Point & p):x(p.x),y(p.y){} Point operator +(Point p){ return Point(x+p.x,y+p.y); } Point operator-(Point p){ return Point(x-p.x,y-p.y); } Point operator*(double d){ return Point(x*d,y*d); } double operator*(Point p){ // 内积 点乘 return x*p.x+ y*p.y; } double operator^(Point p){ // 外积 叉乘 return x*p.y-y*p.x; } friend ostream& operator<<(ostream& os,const Point& p ){ os<
             
              <<" "<
              
               <
               
                >(istream& is, Point&p) { // Point 不能是常量，是变量 is>>p.x>>p.y; return is; } double dist(Point p){ return sqrt( (x-p.x)*(x-p.x)+ (y-p.y)*(y-p.y) ); }};Point intersecting(Point p1,Point p2,Point q1,Point q2){ // 计算直线p1p2与q1q2的交点 double d1=( (q2-q1)^(q1-p1) ); double d2=( (q2-q1)^(p2-p1) ); return p1+ (p2-p1)*(d1/d2) ;}Point p1,p2,q1,q2;void solve() // 判断直线p1p2与直线q1q2的关系{ double d1=(p2-p1)^(q1-p1); double d2=(p2-p1)^(q2-p1); if(fabs(d1 ) < EPS && fabs(d2) < EPS) // 如果p1p2q1 共线 且 p1p2q2 共线 则直线共线 { puts("LINE"); return ; } else { if(fabs( (p2-p1)^(q2-q1) ) < EPS ) // 否则，如果 p1p2 与 q1q2 共线， 则直线平行 { puts("NONE"); return ; } else // 否则，则相交 { Point temp=intersecting(p1,p2,q1,q2); printf("POINT %.2lf %.2lf\n",temp.x,temp.y); } }}int main() { int n; cin>>n; printf("INTERSECTING LINES OUTPUT\n"); for(int i=0;i
                
                 >p1>>p2>>q1>>q2; solve(); } printf("END OF OUTPUT\n"); return 0;}