import scala.collection.mutable.ListBuffer
import scala.util.Random

object ClosestPair {
  case class Point(x: Double, y: Double){
    def distance(p: Point) = math.hypot(x-p.x, y-p.y)

    override def toString = "(" + x + ", " + y + ")"
  }

  case class Pair(point1: Point, point2: Point) {
    val distance: Double = point1 distance point2

    override def toString = {
      point1 + "-" + point2 + ": " + distance
    }
  }

  def sortByX(points: List[Point]) = {
    points.sortBy(point => point.x)
  }

  def sortByY(points: List[Point]) = {
    points.sortBy(point => point.y)
  }

  def divideAndConquer(points: List[Point]): Pair = {
    val pointsSortedByX = sortByX(points)
    val pointsSortedByY = sortByY(points)

    divideAndConquer(pointsSortedByX, pointsSortedByY)
  }

  def bruteForce(points: List[Point]): Pair = {
    val numPoints = points.size
    if (numPoints < 2)
      return null
    var pair = Pair(points(0), points(1))
    if (numPoints > 2) {
      for (i <- 0 until numPoints - 1) {
        val point1 = points(i)
        for (j <- i + 1 until numPoints) {
          val point2 = points(j)
          val distance = point1 distance point2
          if (distance < pair.distance)
            pair = Pair(point1, point2)
        }
      }
    }
    return pair
  }


  private def divideAndConquer(pointsSortedByX: List[Point], pointsSortedByY: List[Point]): Pair = {
    val numPoints = pointsSortedByX.size
    if(numPoints <= 3) {
      return bruteForce(pointsSortedByX)
    }

    val dividingIndex = numPoints >>> 1
    val leftOfCenter = pointsSortedByX.slice(0, dividingIndex)
    val rightOfCenter = pointsSortedByX.slice(dividingIndex, numPoints)

    var tempList = leftOfCenter.map(x => x)