POJ 1269 Intersecting Lines(两直线间关系判定)

POJ 1269 Intersecting Lines(两直线间关系判定)

http://poj.org/problem?id=1269

题意: (ZOJ1280)

给你两条直线(给出4个端点),问你这两条直线之间的关系: 交于一点, 交于直线(即重合), 不相交(平行). 如果交于一点,输出该点的坐标.

分析:

首先假设两直线分别为P+v*t 和Q+w*t. (P,Q分别为直线上的一点,而v和w为直线的方向向量,t取任意实数).

两直线相交于一点<==>Cross(v,w) !=0.

两直线相交于一线<==>Cross(v,w) ==0且 Cross(P-Q,v)==0

两直线相平行<==>Cross(v,w) ==0且 Cross(P-Q,v)!=0

以上结论的证明可以通过看刘汝佳<<训练指南>>自行分析得出.

AC代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double eps=1e-10;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator+(Vector A,Vector B)
{
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator*(Point A,double p)
{
    return Vector(A.x*p,A.y*p);
}
double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double Length(Vector A)
{
    return sqrt(Dot(A,A));
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)
{
    Vector u=P-Q;
    double t=Cross(w,u)/Cross(v,w);
    return P+v*t;
}

int main()
{
    printf("INTERSECTING LINES OUTPUT\n");
    int T; scanf("%d",&T);
    while(T--)
    {
        Point a1,a2,b1,b2;
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a1.x,&a1.y,&a2.x,&a2.y,&b1.x,&b1.y,&b2.x,&b2.y);
        if(dcmp(Cross(a1-a2,b1-b2)) !=0)
        {
            Point P= GetLineIntersection(a1,a2-a1,b1,b2-b1);
            printf("POINT %.2lf %.2lf\n",P.x,P.y);
        }
        else if(dcmp(Cross(a1-b1,a2-a1))==0 ) printf("LINE\n");
        else printf("NONE\n");
    }
    printf("END OF OUTPUT\n");
    return 0;
}