STEP BY STEP

poj 1269 Intersecting Lines

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目意思是给出2条直线，然后判断其是否相交，平行，还是重合。刚开始以为是判断2条线段的关系，用了黑书的模板写了，发现连样例都过不了。后面改了很多才过了。先判断2条直线所在的向量是否平行，这个可以判断这2个向量的叉积是否为0，然后再判断线段是否重合，可以选3点判断叉积是否为0。如果向量不平行的话，直接求交点。求交点的公式是用了黑书里面的方法，先求出2个叉积代表2个三角形的有向面积，然后根据定比分点的关系（面积的比例等于交点分其中一条线段的比例）可以推出计算公式。
有叉积和点积这2个工具确实能方便的解决很多问题。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>
#include <string.h>
#include <math.h>
struct Point
{
    double fX;
    double fY;
};
Point beg[2], end[2];
int nN;
const double fPrecision = 1e-8;

double Det(double fX1, double fY1, double fX2, double fY2)
{
    return fX1 * fY2 - fX2 * fY1;
}

double Cross(Point a, Point b, Point c)
{
    return Det(b.fX - a.fX, b.fY - a.fY, c.fX - a.fX, c.fY - a.fY);
}

int DblCmp(double fD)
{
    if (fabs(fD) < fPrecision)
    {
        return 0;
    }
    else
    {
        return (fD > 0 ? 1 : -1);
    }
}

double DotDet(double fX1, double fY1, double fX2, double fY2)
{
    return fX1 * fX2 + fY1 * fY2;
}

double Dot(Point a, Point b, Point c)
{
    return DotDet(b.fX - a.fX, b.fY - a.fY, c.fX - a.fX, c.fY - a.fY);
}

int BetweenCmp(Point a, Point b, Point c)
{
    return DblCmp(Dot(a, b, c));
}

int SegCross(Point a, Point b, Point c, Point d, Point p)
{
    double s1, s2, s3, s4;
    int d1, d2, d3, d4;
    d1 = DblCmp(s1 = Cross(a, b, c));
    d2 = DblCmp(s2 = Cross(a, b, d));
    d3 = DblCmp(s3 = Cross(c, d, a));
    d4 = DblCmp(s4 = Cross(c, d, b));

    Point e, f;
    e.fX = a.fX - b.fX;
    e.fY = a.fY - b.fY;
    f.fX = c.fX - d.fX;
    f.fY = c.fY - d.fY;
    if (DblCmp(Det(e.fX, e.fY, f.fX, f.fY)) == 0)//2个向量共线
    {
        if (d1 * d2 > 0  d3 * d4 > 0)//不在同一条直线上
        {
            return 0;
        }
        else
        {
            return 2;
        }
    }

    //2条直线相交
    p.fX = (c.fX * s2 - d.fX * s1) / (s2 - s1);
    p.fY = (c.fY * s2 - d.fY * s1) / (s2 - s1);
    return 1;
}

int main()
{
    //freopen("out.txt", "w", stdout);
    while (scanf("%d", &nN) == 1)
    {
        printf("INTERSECTING LINES OUTPUT\n");
        Point p;
        for (int i = 0; i < nN; ++i)
        {
            scanf("%lf%lf%lf%lf", &beg[0].fX, &beg[0].fY, &end[0].fX, &end[0].fY);
            scanf("%lf%lf%lf%lf", &beg[1].fX, &beg[1].fY, &end[1].fX, &end[1].fY);
            int nRet = SegCross(beg[0], end[0], beg[1], end[1], p);
            if (nRet == 0)
            {
                printf("NONE\n");
            }
            else if (nRet == 1)
            {
                printf("POINT %.2f %.2f\n", p.fX, p.fY);
            }
            else
            {
                printf("LINE\n");
            }
        }
        printf("END OF OUTPUT\n");
    }

    return 0;
}

相关文章