POJ 1269 Intersecting Lines (叉积 -- 判断直线位置)

题目链接 ： http://poj.org/problem?id=1269

题意：给出两条直线上的两个点，让你判断两条直线的位置关系，是共线，还是平行，还是相交，若相交则输出交点。

题解 ：这道题，完全就是叉积运用。

我们先判断两直线是否共线，然后在判断是否平行，若以上两条都不满足，那么就是相交。

如何判断直线共线：

        判断共线，那么我们知道，若两个向量的叉积为0，那么两个向量共线。所对于点p1，p2，p3，p4，我们判断向量 p1p2 和向量p1p3 的叉积是否为0 ，并且 p1p3 和 p1p4的叉积是否为0 即可判断是否共线。

如何判断直线平行：

        由于题目给出的是直线上两点，那么我们就可以用两点式，写出直线方程，然后根据斜率判断。

        即 (p1.x - p2.x) * (p3.y - p4.y) == (p1.y - p2.y) * (p3.x - p4.x)

如何求直线交点：

        方法很多，在此提供一种比较简单的解法。

        根据叉积性质，可以知道点P1，P2，Q，若共线，那么就有

        （Q - P1） × （P2 - P1） = 0；

        设两直线交点为C（x0，y0），那么对P1，P2，P3，P4有如下式子

       （Q - P1）× （P2 - P1） = 0；

       （Q - P3）× （P4 - P4） = 0;

         将坐标带入式子。

        向量（（x0 - x1），（y0 - y1））× 向量 (（x2 - x1），(y1 - y2) )  = 0;

        向量（（x0 - x3），（y0 - y3））× 向量 (（x4 - x3），(y4 - y3) )  = 0;

        计算叉乘

        （x0 - x1）* (y1 - y2) - (y0 - y1) * (x2 - x1) = 0;

          (x0 - x3)  *  (y4 - y3) - (y0 - y3) * (y4 - y3) = 0;

        嗯，求解一下二元一次方程组的x，y即可。

看代码：

#include<cmath>
#include<cstdio>

struct node{
	double x,y;
}p1,p2,p3,p4;
double mul(node a,node b ,node c){
	return (c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x);
}
void slove(){
	if(mul(p1,p2,p3) == 0 && mul(p1,p2,p4) == 0)
		printf("LINE\n");
	else if((p1.x - p2.x) * (p3.y - p4.y) == (p1.y - p2.y) * (p3.x - p4.x))
		printf("NONE\n");
	else {
		double a1 = p1.y - p2.y;
		double b1 = p2.x - p1.x;
		double c1 = p1.x * p2.y - p2.x * p1.y;
		double a2 = p3.y - p4.y;
		double b2 = p4.x - p3.x;
		double c2 = p3.x * p4.y - p4.x * p3.y;
		double x = (c1 * b2 - c2 * b1) / (a2 * b1 - a1 * b2);
		double y = (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);
		printf("POINT %.2f %.2f\n",x,y);
	}		
}
int main(){
	int n;
	while(scanf("%d",&n) != EOF){
		printf("INTERSECTING LINES OUTPUT\n");
		while(n -- ){
			scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y,&p3.x,&p3.y,&p4.x,&p4.y);
			slove();
		}
		printf("END OF OUTPUT\n");
	}
	return 0;
}