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

题目来源：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
") ;
    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
" , ix.x ,ix.y) ;
         }
    }
    puts("END OF OUTPUT") ;
   return 0 ;
}

代码如下：

#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include<map>
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<<p.x<<" "<<p.y<<endl;
        return os;
    }
    friend istream& operator>>(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
",temp.x,temp.y);
        }
    }
}

int main() {
    int n;
    cin>>n;
    printf("INTERSECTING LINES OUTPUT
");
    for(int i=0;i<n;i++)
    {
        cin>>p1>>p2>>q1>>q2;
        solve();
    }
    printf("END OF OUTPUT
");
    return 0;
}