这是主要是判断两个直线的平面关系,用到的是向量叉积的运算。
主要是判断时候要注意分清判断的先后顺序,从特殊到一般的顺序进行判断,下面我就直接copy一位网友的解题思路,因为他已经很清晰了。
一、问题描述
http://acm.pku.edu.cn/JudgeOnline/problem?id=1269
题目大意:给两个点能够确定一条直线,题目给出两条直线(由4个点确定),要求判断出这两条直线的关系:平行,同线,相交。如果相交还要求出交点坐标。
二、解题思路
先判断两条直线是不是同线,不是的话再判断是否平行,再不是的话就只能是相交的,求出交点。
如何判断是否同线?由叉积的原理知道如果p1,p2,p3共线的话那么(p2-p1)X(p3-p1)=0。因此如果p1,p2,p3共线,p1,p2,p4共线,那么两条直线共线。direction()求叉积,叉积为0说明共线。
如何判断是否平行?由向量可以判断出两直线是否平行。如果两直线平行,那么向量p1p2、p3p4也是平等的。即((p1.x-p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x-p4.x))==0说明向量平等。
如何求出交点?这里也用到叉积的原理。假设交点为p0(x0,y0)。则有:
(p1-p0)X(p2-p0)=0
(p3-p0)X(p2-p0)=0
展开后即是
(y1-y2)x0+(x2-x1)y0+x1y2-x2y1=0
(y3-y4)x0+(x4-x3)y0+x3y4-x4y3=0
将x0,y0作为变量求解二元一次方程组。
假设有二元一次方程组
a1x+b1y+c1=0;
a2x+b2y+c2=0
那么
x=(c1*b2-c2*b1)/(a2*b1-a1*b2);
y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
因为此处两直线不会平行,所以分母不会为0。
下面贴上自己的代码:
/* Wrote by Dream , poj 1269, double 的零值判断不能直接写==0*/
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct Point
{
double x;
double y;
};
Point p1,p2,p3,p4;
const double ERR = 0.000001;
void DealData();
double Direction(Point p1, Point p2, Point p3);
int main()
{
//freopen("input.txt","r",stdin);
int n = 0;
scanf("%d", &n);
printf("INTERSECTING LINES OUTPUT/n");
for (int i = 0; i < n; ++i)
{
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);
DealData();
}
printf("END OF OUTPUT/n");
return 0;
}
/* p1p2 与 p1p3的叉乘 */
double Direction(Point p1, Point p2, Point p3)
{
return (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);
}
void DealData()
{
if (fabs(Direction(p1,p2,p3)) <= ERR && fabs(Direction(p1,p2,p4)) <= ERR)
{
printf("LINE/n");
}
else if ((p2.x - p1.x) * (p4.y - p3.y) == (p4.x - p3.x) * (p2.y - p1.y))
{
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 = (b1*c2 - b2*c1)/(a1*b2 - a2*b1);
double y = (a2*c1 - a1*c2)/(a1*b2 - a2*b1);
printf("POINT %.2lf %.2lf/n", x, y);
}
}