Problem 102

Triangle Containment

Three distinct points are plotted at random on a Cartesian plane, for which $- 1000 \leq x, y \leq 1000$ , such that a triangle is formed.

Consider the following two triangles:

$A (- 340, 495), B (- 153, - 910), C (835, - 947)$
$X (- 175, 41), Y (- 421, - 714), Z (574, - 645)$

It can be verified that triangle $A B C$ contains the origin, whereas triangle $X Y Z$ does not.

Using triangles.txt (right click and ‘Save Link/Target As…’), a 27K text file containing the co-ordinates of one thousand “random” triangles, find the number of triangles for which the interior contains the origin.

NOTE: The first two examples in the file represent the triangles in the example given above.

包含原点的三角形

在平面直角坐标系中选择三个不同的点，其坐标均满足 $- 1000 \leq x, y \leq 1000$ ，并以这三个点为顶点构成三角形。

考虑如下两个三角形：

$A (- 340, 495), B (- 153, - 910), C (835, - 947)$
$X (- 175, 41), Y (- 421, - 714), Z (574, - 645)$

可以验证三角形 $A B C$ 包含原点，而三角形 $X Y Z$ 不包含原点。

在文本文件triangles.txt中包含了一千个“随机”三角形的坐标，求其中包含原点在其内部的三角形的数目。

注意：文件中的前两个三角形就是上述样例。