POJ 1269 Intersecting Lines解题报告

时间：2010-05-13 来源：MC_ACM

一、问题描述

Sample Input

0 0 4 4 0 4 4 0

5 0 7 6 1 0 2 3

5 0 7 6 3 -6 4 -3

2 0 2 27 1 5 18 5

0 3 4 0 1 2 2 5

Sample Output

INTERSECTING LINES OUTPUT

POINT 2.00 2.00

NONE

LINE

POINT 2.00 5.00

POINT 1.07 2.20

END OF OUTPUT

题目大意：给两个点能够确定一条直线，题目给出两条直线（由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。

三、代码

#include<iostream>
using namespace std;
struct Point
{
    double x,y;
};
Point solve(double a1,double b1,double c1,double a2,double b2,double c2) //求解二元一次方程

{
    Point p;
    p.x=(c1*b2-c2*b1)/(a2*b1-a1*b2);
    p.y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
    return p;
}
double direction(Point p1,Point p2,Point p3) //p1p3,p1p2的叉积

{
    return (p3.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p3.y-p1.y);
}
int N; double a1,b1,c1,a2,b2,c2;
Point p1,p2,p3,p4; Point p0;//交点

int main()
{
    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);
        if(direction(p3,p4,p1)==0 && direction(p3,p4,p2)==0)//共线

            printf("LINE\n");
        else
        {
            if( ((p1.x-p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x-p4.x))==0 )//平行

                printf("NONE\n");
            else
            {
                a1=p1.y-p2.y;b1=p2.x-p1.x;c1=p1.x*p2.y-p2.x*p1.y;
                a2=p3.y-p4.y;b2=p4.x-p3.x;c2=p3.x*p4.y-p4.x*p3.y;
                p0=solve(a1,b1,c1,a2,b2,c2);
                printf("POINT %.2f %.2f\n",p0.x,p0.y);
            }
        }
    }
    printf("END OF OUTPUT\n");
    return 0;
}