let n = 30
let spots = []
let closest = []
let playground = document.querySelector('.playground')

function createSpots () {
  let px = 16
  let minX = minY = px
  let maxX = window.innerWidth - px
  let maxY = window.innerHeight - px
  
  let checkSpot = (x, y) => {
    let size = spots.length
    for (let i = 0; i < size; i++) {
      let d = getSpotsDistance(x, spots[i].x, y, spots[i].y)
      if (d < 16 * 16) { 
        return false
      }
    }
    return true
  }
  
  for(let i = 0; i < n; i++) {
    let span = document.createElement('span')
    let x, y
    
    while (true) {
      x = getRandomPoint(minX, maxX)
      y = getRandomPoint(minY, maxY)
    
      if (checkSpot(x, y)) {
        spots.push({
          x: x,
          y: y
        })
        break
      }
    }
    
    span.className = 'spot'
    setTimeout(() => {
      span.style.transform = 'translate(' + x + 'px,' + y + 'px)'      
    }, 0)
   
    playground.appendChild(span)
  }
}

function getRandomPoint (min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function getSpotsDistance (x1, x2, y1, y2) {
  return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
}

createSpots()

/////////////

function solve () {
  let distance = (p1, p2) => {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)
  }
  
  let ans
  spots.sort((a, b) => {
    if(a.x < b.x) {
      return -1
    } else {
      return 1      
    }
  })
  let candidate = new TreeSet((p1, p2) => {
    if (p1.y == p2.y) {
      if (p1.x < p2.x) {
        return -1
      } else {
        return 1
      }
    } else {
      return p1.y < p2.y ? -1 : 1
    }
  })

  candidate.add(spots[0])
  candidate.add(spots[1])
  ans = distance(spots[0], spots[1])
  
  let start = 0
  for(let i = 2; i < n; i++) {
    let now = spots[i]
    while(start < i) {
      let pivot = spots[start]
      let x = pivot.x - now.x
      
      if (x * x > ans) {
        candidate.remove(pivot)
        start += 1
      } else {
        break
      }
    }
    
    let d = parseInt(Math.sqrt(ans) + 1)
    let lower = lower_bound(candidate.elements, now.y - d)
    let upper = upper_bound(candidate.elements, now.y + d)

    for (let i = lower; i < upper; i++) {
      if (candidate.elements.length == 0) break
      d = distance(now, candidate.elements[i])
      if (d < ans) {
        closest[0] = {x: now.x, y: now.y}
        closest[1] = {x: candidate.elements[i].x, y: candidate.elements[i].y}
        ans = d
      }
    }
    candidate.add(now)
  }
  return candidate
}

function lower_bound(array, target) {
  let low = 0, high = array.length - 1
  while (low < high) {
    let mid = low + parseInt((high - low) / 2)
    if (array[mid].y < target) {
      low = mid + 1
    } else {
      high = mid
    }
  }
  return low
}

function upper_bound(array, target) {
  let low = 0, high = array.length - 1
  while (low < high) {
    let mid = low + parseInt((high + 1 - low) / 2)
    if (array[mid].y > target) {
      high = mid - 1
    } else {
      low = mid
    }
  }
  return low + 1
}

class TreeSet {

  constructor (compatator) {
    this.elements = []
    if (compatator) {
      this.compatator = compatator
    } else {
      this.compatator = (a, b) => { return a - b }
    }
  }

  add (element) {
    let index = this.binarySearch(element)
    if (index < 0) {
      index = -index - 1
    }
    this.elements.splice(index, 0, element)
  }
  
  remove (element) {
    let len = this.elements.length
    let index = 0    
    for(let i = 0; i < len; i++) {
      if (this.elements[i].x === element.x && this.elements[i].y === element.y) {
        index = i
        break
      }
    }
    this.elements.splice(index, 1)
  }
  
  binarySearch (value) {
    let low = 0
    let high = this.elements.length - 1

    while (low <= high) {
      let mid = (low + high) >>> 1
      let midValue = this.elements[mid]
      let cmp = this.compatator(midValue, value)
      if (cmp < 0) {
        low = mid + 1
      } else if (cmp > 0) {
        high = mid - 1
      } else {
        return mid
      }
    }
    return -(low + 1)
  }
}

let c = solve()

if (closest.length == 0) {
  closest[0] = spots[0]
  closest[1] = spots[1]
}

for (let i = 0; i < 2; i++) {
  let span = document.createElement('span')
  let x, y

  span.className = 'closest'
  setTimeout(() => {
    span.style.transform = 'translate(' + closest[i].x + 'px,' + closest[i].y + 'px)'      
  }, 1000)

  playground.appendChild(span) 
}