AOJ 0585 Nearest Two Points

xy平面上に点がn個あり、ある2個を選んだときの距離のうち最小のものを求める問題です。
分割統治法を使って解く有名問題でしたが、JOIによる解説は枝刈り全探索でした。
枝刈りを使って解いた方のソースコードがAOJで見られなくなったので、こちらに置いておきます（実行時間7.55s / 制限時間8.00s）

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
static const int MAX_N = 500000;
static const int INF = 1e9;

int main(){
  int n;
  P A[MAX_N]; // firstをx座標、secondをy座標とする
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> A[i].first >> A[i].second;
  }
  sort(A, A + n); // x座標に関して昇順にソートする
  int L = INF; // 2点間の最短距離を記録する為の変数
  for(int i = 1; i < n; i++){ // 各点から開始し、負の方向に向けて全探索を行う
    for(int j = i - 1; j >= 0; j--){
      if((A[i].first - A[j].first) > L) break; // x方向の距離が現時点での最短距離を上回っていたら、それ以降の探索を打ち切る
      int d2 = (A[i].first - A[j].first) * (A[i].first - A[j].first) + (A[i].second - A[j].second) * (A[i].second - A[j].second);
      if(d2 < L) L = d2;
    }
  }
  cout << L << endl;
  return 0;
}