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.



In [15]:

    
open System.IO

let readLines (filePath:string) = seq {
    use sr = new StreamReader (filePath)
    while not sr.EndOfStream do
        yield sr.ReadLine ()
}

let rawTriangles =
    readLines "resources/p102_triangles.txt"
    |> Seq.map (fun s -> s.Replace("\"",""))
    |> Seq.map (fun s -> s.Split([|','|]))
      
    
let sign (x1,y1) (x2,y2) (x3,y3) =
    ((x1-x3) * (y2-y3)) - ((x2-x3) * (y1-y3))
    
let containsOrigin v1 v2 v3 =
    let b1 = (sign (0,0) v1 v2) < 0
    let b2 = (sign (0,0) v2 v3) < 0
    let b3 = (sign (0,0) v3 v1) < 0   
    (b1 = b2) && (b2 = b3)

let processRawTriangle rawTriangle = 
    let vertices = rawTriangle |> Array.map int
    let v1 = (vertices.[0], vertices.[1])
    let v2 = (vertices.[2], vertices.[3])
    let v3 = (vertices.[4], vertices.[5])
    containsOrigin v1 v2 v3    

rawTriangles
|> Seq.filter processRawTriangle
|> Seq.length









    Out[15]:





228



In [ ]: