Analysis: Square Overlap by Travis Hance

Among the given points, we want to look for points (x1, y1) and (x2, y2) such that |x1 - x2| <= k-1 and |y1 - y2| <= k-1. To do this we use a plane sweep. Imagine a vertical strip of width k-1, say from x-k+1 to x. As x increases, we maintain the set of points contained in the strip. Each time a new point (x1, y1) enters the strip, we check for points (x2, y2) in the strip with |y1 - y2| <= k-1. We can do this if we maintain the set of points in the strip using a binary search tree (e.g., TreeSet in Java or STL's set in C++).

We also need to delete points when they leave the strip. We could use a priority queue, keyed by x-coordinate, to help us learn when points need to be deleted. Alternatively, we could use lazy deletion, only deleting points from the set when we come across them.

Here is Mark Gordon's solution in C++: 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstdio>

using namespace std;

int main() {
  freopen("squares.in", "r", stdin);
  freopen("squares.out", "w", stdout);
  int N, K; cin >> N >> K;

  vector<pair<int, int> > S;
  for(int i = 0; i < N; i++) {
    int x, y; cin >> x >> y;
    S.push_back(make_pair(x, y));
  }
  sort(S.begin(), S.end());

  set<pair<int, int> > st;
  vector<pair<int, int> > res;
  set<pair<int, int> >::iterator ita, itb;
  for(int i = 0, j = 0; i < S.size() && res.size() < 2; i++) {
    for(; S[j].first + K <= S[i].first; j++) {
      st.erase(make_pair(S[j].second, j));
    }

    ita = itb = st.insert(make_pair(S[i].second, i)).first;
    if(ita-- != st.begin() && S[i].second < ita->first + K) {
      res.push_back(make_pair(i, ita->second));
    }
    if(++itb != st.end() && itb->first < S[i].second + K) {
      res.push_back(make_pair(i, itb->second));
    }
  }

  long long result = 0;
  if(res.size() > 1) {
    result = -1;
  } else if(res.size() == 1) {
    int dx = S[res[0].first].first - S[res[0].second].first;
    int dy = S[res[0].first].second - S[res[0].second].second;
    if(dx < 0) dx = -dx;
    if(dy < 0) dy = -dy;
    result = 1ll * (K - dx) * (K - dy);
  }
  cout << result << endl;
}