ClosestPair.scala

case class Point(x: Double, y: Double)

def distance(pair: Option[(Point, Point)]): Double = {
  pair match {
    case None => Double.MaxValue
    case Some((p1, p2)) => Math.sqrt( Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2) )
  }
}

def closestPair(points: List[Point]): Option[(Point, Point)] = {
  if (points.size <= 1) return None

  val mostLeft = points.minBy(_.x)
  val mostRight = points.maxBy(_.x)
  val middle = (mostLeft.x + mostRight.x) / 2.0

  val minPairLeft = closestPair(points.filter(_.x < middle))
  val minPairRight = closestPair(points.filter(_.x >= middle))

  val minPairSide = List(minPairLeft, minPairRight).minBy(distance)
  val minPairSideDistance = distance(minPairSide)

  val middlePoints = points.filter( p => p.x < middle + minPairSideDistance && p.x > middle - minPairSideDistance)
  val middlePointSortedByY = middlePoints.sortBy(_.y)
  val possiblePairMiddle = for {  first <- middlePointSortedByY
                                  second <- middlePointSortedByY if (second != first && second.y < first.y + minPairSideDistance)}
    yield (first, second)

  val minPairMiddle = if (possiblePairMiddle.isEmpty) None
                      else possiblePairMiddle.map(Some(_)).minBy(distance)

  List(minPairMiddle, minPairSide).minBy(distance)
}