
object Main extends App{
  import scala.io.StdIn._
  val n: Int = readLine.trim.toInt
  val pointsSortByX = Array.tabulate(n){_ ⇒ val Array(x, y) = readLine.trim.split(' ').map(_.toInt); Point(x, y)}.sortBy{_.x}
  val pointsSortByY = pointsSortByX.sortBy(_.y)
  pointsSortByX.zipWithIndex.foreach{case (p, i) ⇒ p.rankX = i}
  println(minDistanceSquare(pointsSortByX, pointsSortByY))
  def minDistanceSquare(pointsSortByX: Array[Point], pointsSortByY: Array[Point]): Long = {
    pointsSortByX.length match{
      case 0 ⇒ Int.MaxValue
      case 1 ⇒ Int.MaxValue
      case 2 ⇒ pointsSortByX(0).distanceSquare(pointsSortByX(1))
      case n ⇒
        val mid = pointsSortByX(n / 2)
        val leftX = Array.tabulate(n / 2){i ⇒ pointsSortByX(i)}
        val leftY = pointsSortByY.filter{_.rankX < n / 2}
        val leftMin = minDistanceSquare(leftX, leftY)
        val rightX = Array.tabulate(n - n / 2 - 1){i ⇒ pointsSortByX(n / 2 + 1 + i)}
        val rightY = pointsSortByY.filter{_.rankX > n / 2}
        val rightMin = minDistanceSquare(rightX, rightY)
        val minHalf = if (leftMin < rightMin) leftMin else rightMin
        val suspectLeft = leftX.filter{p ⇒ mid.x - minHalf <= p.x && mid.x + minHalf >= p.x && mid.y - minHalf <= p.y && mid.y + minHalf >= p.y}
        val suspectRight = rightX.filter{p ⇒ mid.x - minHalf <= p.x && mid.x + minHalf >= p.x && mid.y - minHalf <= p.y && mid.y + minHalf >= p.y}
        val minAcross = if (suspectLeft.isEmpty || suspectRight.isEmpty) Int.MaxValue else suspectLeft.map{l ⇒ suspectRight.map{r ⇒ l.distanceSquare(r)}.min}.min
        val minMid = if (suspectLeft.isEmpty && suspectRight.isEmpty) Int.MaxValue else List(suspectLeft, suspectRight).filterNot{_.isEmpty}.flatMap{_.map{p ⇒ p.distanceSquare(mid)}}.min
        List(minMid, minAcross, minHalf).min
    }
  }
}
case class Point(x: Long, y: Long) {
  var rankX: Int = 0
  var rankY: Int = 0
  def distanceSquare(that: Point): Long = (x - that.x) * (x - that.x) + (y - that.y) * (y - that.y)

}
