本文主要是介绍POJ1269 判断2条直线的位置关系,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目大意:给两个点能够确定一条直线,题目给出两条直线(由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
------------------------------------------------------------------------
叉乘不满足交换律
const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
}struct Point{double x , y ;Point(){}Point(double _x , double _y):x(_x),y(_y){}Point operator + (Point o){return Point(add(x , o.x) , add(y , o.y)) ;}Point operator - (Point o){return Point(add(x , -o.x) , add(y , -o.y)) ;}Point operator * (double o){return Point(x*o , y*o) ;}double operator ^(Point o){return add(x*o.y , -y*o.x) ;}double dist(Point o){return sqrt((x-o.x)*(x-o.x) + (y-o.y)*(y-o.y)) ;}void read(){scanf("%lf%lf" ,&x , &y) ;}
};//判断2条直线的位置关系
int twoline(Point p1 , Point p2 , Point q1 , Point q2 , Point &interp){if(fabs((p2-p1) ^ (q1-p1)) < eps &&fabs((p2-p1) ^ (q2-p1)) < eps ) return 1 ; //共线if(fabs((p2-p1) ^ (q2-q1)) < eps) return 2 ; //平行double d1 = (q2 - q1) ^ (q1 - p1) ;double d2 = (q2 - q1) ^ (p2 - p1) ;double t = d1 / d2 ;interp = p1 + (p2 - p1) * t ; // 交点 interpreturn 3 ; // 相交
}int main(){int t , k ;Point p1 , p2 , q1 , q2 , interp ;puts("INTERSECTING LINES OUTPUT") ;cin>>t ;while(t--){p1.read() , p2.read() ;q1.read() , q2.read() ;k = twoline(p1 , p2 , q1 , q2 , interp) ;if(k == 1) puts("LINE") ;else if(k == 2) puts("NONE") ;else printf("POINT %.2lf %.2lf\n" , interp.x , interp.y) ;}puts("END OF OUTPUT") ;return 0 ;
}
这篇关于POJ1269 判断2条直线的位置关系的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!