/**
 * 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
 */

import Foundation

struct AuD_12_04_MinDist {

    struct Point {
        let x: Int
        let y: Int
        init(_ x: Int, _ y: Int) {
            self.x = x
            self.y = y
        }
        func distTo(_ other: Point) -> Double {
            ((Double(x)-Double(other.x))*(Double(x)-Double(other.x))
                + (Double(y)-Double(other.y))*(Double(y)-Double(other.y))).squareRoot()
        }
    }

    static func minDistBF(_ a: [Point]) -> Double {
        var mindist = Double(Int.max)
        for i in 1 ..< a.count-1 {
            for j in i+1 ..< a.count {
                let dist = a[i].distTo(a[j])
                mindist = Double.minimum(mindist, dist)
            }
        }
        return mindist
    }

    static func minDistTH(_ a: [Point], _ l: Int, _ r: Int) -> Double {
        if (l == r) {
            return Double(Int.max)
        } else {
            let m: Int = Int(ceil((Double(l) + Double(r)) / 2.0))
            var mindist = Double.minimum(minDistTH(a, l, m - 1), minDistTH(a, m, r))
            for i in 1 ..< m {
                for j in m ..< a.count {
                    let dist = a[i].distTo(a[j])
                    mindist = Double.minimum(mindist, dist)
                }
            }
            return mindist
        }
    }

    static let points = [
        (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( { (p) in Point(p.0, p.1) } )

    static func run() {
        print(minDistBF(points)) // 1.0
        print(minDistTH(points, 0, points.count-1)) // 1.0
    }
}