Triangle containment

2017-11-20

Problem 102: Triangle containment

Description:

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, 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.

Solution:

003p>013p>053p023p033p143p>23g13g9+g:59*-!#v_:48*-!#v_  :92+4*-!#v_vv1g55*-g50g<
         |-***8555<       ^p32+1g32<p341p33 0p5p35+1 :g35*g34g33$< v5>45g05g-25^
         >03g.@                    ^p34-10$<vp33    $# +*+55g33-*86<g^p40+*:-g5<
$$$$$$  >13g1+:13p^                ^        <       >33g43g*53g5p45g 05g-:*55g1^
XXXXXXX  v+*:-g51g53*:-g50g52p42+*g51-g51g55*g50-g50g54p41+*-g51g53-<
OOOOOO   >34p25g05g-05g*35g15g-15g*+44p14g44g*34g24g*-54p14g24g*04g4v
        ^p30+g30!++!`+g45g46g47`g460`g450p47-*g41g41*g43g40p46-*g4  <

-340,495,-153,-910,835,-947
-175,41,-421,-714,574,-645
-547,712,-352,579,951,-786
419,-864,-83,650,-399,171
-429,-89,-357,-930,296,-29
-734,-702,823,-745,-684,-62
...
...
...

Download

This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Not much to say here, a bit of input parsing, then looping through all lines and testing the triangles with this basic algorithm.

Because the program is already pretty fast we don't spend much time optimizing it, that means most variables have fixed grid values, even though I could optimize a few to live only on the stack.