open System let dist (x1,y1) (x2,y2) = Math.Sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) let closestBf points = let n = Seq.length points let list = points |> Seq.toList seq { for i in 0..n-2 do for j in i+1..n-1 do yield list.[i], list.[j] } |> Seq.minBy (fun (a, b) -> dist a b) let rec closestInternal points = match points with | _ when points |> Seq.length < 4 -> closestBf points | _ -> //partition points about a vertical line let sorted = points |> Seq.sortBy(fun (x,y) -> x) let left = sorted |> Seq.take((points |> Seq.length)/2) let right = sorted |> Seq.skip((points |> Seq.length)/2) //recurse each side of the vertical line let lMin = closestInternal left let rMin = closestInternal right //find minimum distance between closest pairs on each side of the line let lDist = match lMin with | (a,b) -> dist a b let rDist = match rMin with | (a,b) -> dist a b let minDist = Math.Min(lDist,rDist) let dividingX = left |> Seq.toList |> List.rev |> List.head |> fst //find close points on the right to the dividing line let closePoints = right |> Seq.takeWhile(fun (x,y) -> x - dividingX < minDist) |> Seq.sortBy(fun (x,y) -> y) //take the close points and merge them with the close points to the dividing line on the left hand side let pairs = left |> Seq.skipWhile(fun (x,y) -> dividingX - x > minDist) |> Seq.collect(fun (x,y) -> closePoints |> Seq.skipWhile(fun (x1,y1) -> y1 < y - minDist) |> Seq.takeWhile(fun (x2,y2) -> y2 < y + minDist) |> Seq.map(fun a -> ((x,y),a))) |> Seq.toList //return the closest pair of points from the three groups pairs |> List.append [lMin;rMin] |> List.sortBy(fun (a,b) -> dist a b) |> List.head