0%

Problem 102


Problem 102


Triangle containment

Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 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 ABC contains the origin, whereas triangle XYZ 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 ≤ x, y ≤ 1000,这三个点构成一个三角形。

考虑下面两个三角形:

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

可以验证三角形ABC包含原点,而三角形XYZ不包含原点。

在27K的文本文件triangles.txt(右击并选择“目标另存为……”)中包含了一千个“随机”三角形的坐标,找出其中包含原点在其内部的三角形的数量。

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