#include <string>
#include <vector>
#include <map>
#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;

class MinimumSquare {
  public:
    long long minArea(vector <int> x, vector <int> y, int k);

    vector<long long> XV_V;         // The unique X values in order, sentinelized on both sides.
    vector<long long> YV_V;         // The unique Y values in order, sentinelized on both sides.

    map <long long, long long> XV;  // Values in XV_V.  XV[XV[i]] = i.
    map <long long, long long> YV;  // Values in YV_V.  YV[YV[i]] = i.

    vector < vector <long long> > Pts_In_Rect;   // Pts_In_Rect[i][j] stores the number of points
                                                 // whose x values are <= XV_V[j] and
                                                 // whose y values are <= YV_V[i].

    long long Maxwidth;                          // Maximum width of a square, over all points.
    long long K;                                 // Target number of points.

    /* Pts_In_Square() returns the number of points in the square with the given width, whose
       lower left-hand corner is ( XV_V[xindex], YV_V[yindex] ).  It is O(log(n)). */

    long long Pts_In_Square(int xindex, int yindex, long long width);

    /* Do_Binary_Search() does a binary search over all widths to
       find the smallest one that has at least K points when its lower
       left-hand corner is ( XV_V[xindex], YV_V[yindex] ).  If there is no
       such width, it will return (Maxwidth+1) */
 
    long long Do_Binary_Search(long long xindex, long long yindex);
};

/* The binary search.  Starts with low = 0, and high = Maxwidth.  Your invariant
   will be that Pts_In_Square(xindex, yindex, low) is < K, and 
                Pts_In_Square(xindex, yindex, high) is >= K.  

   If either of these if false to start with, you can return.  Otherwise, you keep
   checking the middle of low and high, and then updating low or high accordingly.
   You stop when low = high-1, and you return high, because that is the smallest
   width that has enough points in it. */

long long MinimumSquare::Do_Binary_Search(long long xindex, long long yindex)
{
  long long low, mid, high;

  low = 0;
  high = Maxwidth;
  
  if (Pts_In_Square(xindex, yindex, high) < K) return Maxwidth+1;
  if (Pts_In_Square(xindex, yindex, low) >= K) return low;

  while (1) {
    if (high == low + 1) return high;
    mid = (high + low) / 2;
    if (Pts_In_Square(xindex, yindex, mid) >= K) {
      high = mid;
    } else {
      low = mid;
    }
  }
  return -1;
}

/* Best to look at the lecture notes for this one -- you use upper_bound() to 
   find the high x and y points.  The fact that you have sentinelize this helps,
   because you know that upper_bound will always return a legal iterator.  
   Then use the equation of four values involving Pts_In_Rect. */

long long MinimumSquare::Pts_In_Square(int xindex, int yindex, long long width)
{
  map <long long, long long>::iterator xit;
  map <long long, long long>::iterator yit;
  int xh, yh;
  long long x, y;

  x = XV_V[xindex];
  y = YV_V[yindex];

  xit = XV.upper_bound(x+width);
  xh = xit->second-1;
  
  yit = YV.upper_bound(y+width);
  yh = yit->second-1;
  
  return Pts_In_Rect[yh][xh] - Pts_In_Rect[yh][xindex-1]
                            - Pts_In_Rect[yindex-1][xh]
                            + Pts_In_Rect[yindex-1][xindex-1];
}

long long MinimumSquare::minArea(vector <int> x, vector <int> y, int k)
{

  map <long long, long long>::iterator xit, yit;
  long long i, j, w, row, col, min, bestw, mw;

  K = k;

  /* Insert the unique X and Y values into XV and YV respectively.
     Give them values of zero. */

  for (i = 0; i < x.size(); i++) {
    XV[x[i]] = 0;
    YV[y[i]] = 0;
  }

  /* Calculate the maximum possible width of a square. */

  i = XV.rbegin()->first - XV.begin()->first;
  j = YV.rbegin()->first - YV.begin()->first;
  Maxwidth = (i > j) ? i : j;

  /* Sentinelize them, so that there is a minimum value in each map that
     doesn't correspond to any point, and so that there is a maximum value
     that will be bigger than any possible maximum value.  */

  min = XV.begin()->first;
  XV[min-1] = 0;
  XV[0xffffffffffffLL] = 0;

  min = YV.begin()->first;
  YV[min-1] = 0;
  YV[0xffffffffffffLL] = 0;

  /* Now create the vals, so that the i'th entry in each map has an val of i; */

  i = 0;
  for (xit = XV.begin(); xit != XV.end(); xit++) {
    xit->second = i;
    i++;
  }

  i = 0;
  for (yit = YV.begin(); yit != YV.end(); yit++) {
    yit->second = i;
    i++;
  }

  /* Create vectors XV_V and YV_V, which have the keys from XV and YV, respectively.
     You'll note that XV[XV_V[i]] equals i, and YV[YV_V[i]] equals i. */
 
  for (xit = XV.begin(); xit != XV.end(); xit++) XV_V.push_back(xit->first);
  for (yit = YV.begin(); yit != YV.end(); yit++) YV_V.push_back(yit->first);
  
  /* Error check */

  // for (i = 0; i < XV_V.size(); i++) printf(" %d", XV_V[i]);  printf("\n");
  // for (i = 0; i < YV_V.size(); i++) printf(" %d", YV_V[i]);  printf("\n");

  /* Create the matrix Pts_In_Rect.  This is a four-step activity.  

     1.  Allocate the matrix and put all zeros into it.  
     2.  For every point in the problem, set its entry in Pts_In_Rect to 1.  
     3.  For every element (i,j) in the matrix with i and j > 0, set the element to
         the sum of its value and the value in the column to the left of it.
         At the end of this step, Pts_In_Rect[i][j] contains the number of points
         in row i whose x values are <= XV[j].
     4.  Lastly for every element (i,j) in the matrix with i and j > 0, set the
         element to the sum of its value and the value in the row above it.
         Now, Pts_In_Rect[i][j] contains what we want -- the number of points whose
         x values are <= XV[j] and whose y values are <= YV[i].  */
         
  /* Step 1 */

  Pts_In_Rect.resize(YV_V.size());
  for (i = 0; i < Pts_In_Rect.size(); i++) {
    Pts_In_Rect[i].resize(XV_V.size(), 0);
  }

  /* Step 2 */

  for (i = 0; i < x.size(); i++) {
    col = XV[x[i]];
    row = YV[y[i]];
    Pts_In_Rect[row][col] = 1;
  }
  
  /* Step 3 */

  for (i = 1; i < Pts_In_Rect.size(); i++) {
    for (j = 1; j < Pts_In_Rect[i].size(); j++) {
      Pts_In_Rect[i][j] += (Pts_In_Rect[i][j-1]);
    }
  }

  /* Step 3 */

  for (j = 1; j < Pts_In_Rect[0].size(); j++) {
    for (i = 1; i < Pts_In_Rect.size(); i++) {
      Pts_In_Rect[i][j] += (Pts_In_Rect[i-1][j]);
    }
  }

  /* Error check -- print out the values. */

  /*
  for (i = 0; i < Pts_In_Rect.size(); i++) {
    for (j = 0; j < Pts_In_Rect[i].size(); j++) printf(" %2lld", Pts_In_Rect[i][j]);
    printf("\n");
  } */
  
  /* Now, for each x value, and each y value, do a binary search starting with
     a low width of 0 and a high width of maxwidth, and find the smallest value
     of w such that Pts_In_Square(x,y,w) >= K. */

  bestw = Maxwidth;

  for (i = 1; i < XV.size()-1; i++) {
    for (j = 1; j < YV.size()-1; j++) {
      mw = Do_Binary_Search(i, j);
      if (mw < bestw) bestw = mw;
    }
  }

  /* Add two, because the problem wants squares where the points aren't on the 
     borders of the square, and we calculated squares where the points are on 
     border. */

  bestw += 2;
  return (bestw * bestw);
}