Triangle containment

Fork me on GitHub

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

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  <

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


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.

Interpreter steps: 1 995 449
Execution time (BefunExec): 281ms (7.10 MHz)
Program size: 80 x 1009
Solution: 228
Solved at: 2017-11-20

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript