Solution Notes: We first sort all the points on x, then sweep a pair of vertical "sweep lines" from left to right through the scene. The y values of points between the sweep lines are stored in a data structure that can quickly find the min and max, such as an STL multiset (which we have used below) or a pair of priority queues. Whenever the difference between the max and min y coordinates is at least D, we check if this represents the best flowerpot width so far, and then advance the left sweep line; otherwise, we advance the right sweep line. The total running time is O(N log N).

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#define INF 2000000000

using namespace std;

typedef pair<int,int> Point;
multiset<int> Window;
int N, D;

int get_min(void) { return *(Window.begin()); } 
int get_max(void) { return *(Window.rbegin()); }

int main(void)
{
  int i, j, x, y, ans=INF;
  vector<Point> P;
  
  freopen ("fpot.in", "r", stdin);
  freopen ("fpot.out", "w", stdout);
  
  scanf ("%d %d", &N, &D);
  for (i=0; i<N; i++) {
    scanf ("%d %d", &x, &y);
    P.push_back(make_pair(x,y));
  }
  sort(&P[0], &P[N]);

  i=j=0;
  Window.insert(P[0].second);
  while(1) {
    if (get_max() - get_min() >= D) {
      if (P[j].first-P[i].first < ans) ans = P[j].first-P[i].first;
      multiset<nt>::iterator iter(Window.find(P[i++].second));
      Window.erase(iter);
    } else { 
      if (j==N-1) break;
      Window.insert(P[++j].second);
    }
  }

  printf ("%d\n", ans==INF ? -1 : ans);
  
  return 0;
}