一点一点前进...

0%

判断一个点是不是在某个三角形内 | 欧拉项目 | 102题

发表于 分类于 ， Disqus：

题目是：文件中的三角形中有多少个内部包含原点？

在笛卡尔平面上随机取三个不同的点，其中-1000 ≤ x, y ≤ 1000，会形成一个三角形。
考虑如下两个三角形：
A(-340,495), B(-153,-910), C(835,-947)
X(-175,41), Y(-421,-714), Z(574,-645)
可以证明三角形ABC包含原点在其内部，而三角形XYZ则不包含。
triangles.txt 包含一千个随机三角形，求其中有多少个三角形的内部包含原点。

如何判断一个点是不是在某个三角形内呢？
一个不太笨的方法是，如果点C和点O在直线AB的同侧，点B和点O在直线AC的同侧，点A和点O在直线BC同侧，那么点O就在三角形ABC里面。
好了，问题转化为，如何判断两个点在某直线的同侧。
算法导论中有说这个问题，向量AB和向量AC叉积，向量AB和向量AO叉积，如果两个叉积结果的符号相同，那么说明点C和点O在AB的同侧。
思路都解释完了，下面写代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
private static bool IsSameSide(int xa, int ya, int xb, int yb, int xc, int yc, int xo, int yo)
{
    return (long)CrossProduct(xa, ya, xb, yb, xc, yc) * CrossProduct(xa, ya, xb, yb, xo, yo) > 0;
}

private static int CrossProduct(int xa, int ya, int xb, int yb, int xc, int yc)
{
    int xv = xb - xa;
    int yv = yb - ya;
    int xu = xc - xa;
    int yu = yc - ya;
    return xv * yu - yv * xu;
}

需要解释的是，坐标小于1000，叉积结果大约是十的六次方数量级，IsSameSide判断的时候如果不强转成long型，可能会溢出，造成判断错误。

给出的数据比较大，需要写一点点代码去解析它们。
下面是完成的代码： 

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
int count = 0;
string[] triangles = Triangles.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);

int xo = 0;
int yo = 0;

foreach (string triangle in triangles)
{
    int[] tmp = triangle.Split(',').Select(s => int.Parse(s)).ToArray();

    int xa = tmp[0];
    int ya = tmp[1];
    int xb = tmp[2];
    int yb = tmp[3];
    int xc = tmp[4];
    int yc = tmp[5];

    if (IsSameSide(xa, ya, xb, yb, xc, yc, xo, yo)
        && IsSameSide(xa, ya, xc, yc, xb, yb, xo, yo)
        && IsSameSide(xb, yb, xc, yc, xa, ya, xo, yo))
    {
        count++;
    }
}

return count;