在平面直角坐标系中选择三个不同的点，其横、纵坐标均在$[-1000,1000]$内，并以这三个点为顶点构成三角形。例如： $$A(-340,495), B(-153,-910), C(835,-947)$$ $$X(-175,41), Y(-421,-714), Z(574,-645)$$ 可以验证可以验证原点在三角形ABC内，但不在三角形XYZ内。

在文件triangles.txt中有一千个这样的三角形的坐标，求其中内部包含原点的三角形的总数。

注：文件中的前两个三角形就是上面这两个例子。

本题难度:

解答

点在凸边形内当且仅当其对于边界上指定的正方向而言该点都在各边界向量的同一侧。对本题而言，设三顶点分别是A、B、C，按顺时针或逆时针依次连接得边界向量$\overrightarrow{AB}$, $\overrightarrow{BC}$, $\overrightarrow{CA}$，分别以这些向量为方向向量可得三直线方程 $$L_i: a_ix+b_iy+c_i=0, \quad i=1,2,3$$ 每条直线把平面分成三部分： $$\begin{cases} H_i^+=\{(x,y): a_ix+b_iy+c_i > 0\}, \\ H_i^-=\{(x,y): a_ix+b_iy+c_i < 0\}, \\ L_i=\{(x,y): a_ix+b_iy+c_i = 0\}. \end{cases}$$ 若点在三角形内部，则将其代入直线方程后，或者都在$H_i^{+}$中，或者都在$H_i^{-}$中。如此则得结果是$228$。

d=[]
with open("102_triangles.txt") as f:
    for line in f:
        d.append([int(i) for i in line.split(",")])
s=0
for a1,a2,b1,b2,c1,c2 in d:
    u=(b2-a2)*(0-a1)-(b1-a1)*(0-a2)
    v=(c2-b2)*(0-b1)-(c1-b1)*(0-b2)
    w=(a2-c2)*(0-c1)-(a1-c1)*(0-c2)
    if (u > 0 and v > 0 and w > 0) or (u < 0 and v < 0 and w < 0):
        s+=1
print s