package kapitel_12

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 12, Teilen und Herrschen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_12_04_MinDist_App extends App {

  case class Point(x: Int, y: Int) {
    def distTo(other: Point) =
      Math.sqrt((x-other.x)*(x-other.x) + (y-other.y)*(y-other.y))
  }

  def minDistBF(a: Array[Point]): Double = {
    var mindist = Double.MaxValue
    for (i <- 1 until a.length-1) {
      for (j <- i+1 until a.length) {
        val dist = a(i).distTo(a(j))
        mindist = Math.min(mindist, dist)
      }
    }
    mindist
  }

  def minDistTH(a: Array[Point], l: Int, r: Int): Double =
    if (l == r) {
      Double.MaxValue
    } else {
      val m = Math.ceil((l.toDouble + r.toDouble) / 2.0).toInt
      var mindist = Math.min(minDistTH(a, l, m - 1), minDistTH(a, m, r))
      for (i <- 1 until m) {
        for (j <- m until a.length) {
          val dist = a(i).distTo(a(j))
          mindist = Math.min(mindist, dist)
        }
      }
      mindist
    }

  val points = Array(
    (1,1),(10,1),(6,2),(3,3),(6,5),(3,6),(10,6),(1,9),(7,9),(10,10),(4,4),(6,4)
  ).map {case (x,y) => Point(x,y) }

  println(minDistBF(points)) // 1.0
  println(minDistTH(points, 0, points.length-1)) // 1.0
}