Implementation of the algorithm which finds a pair of closest points on the plane using nlogn operations

closestPairOfPoints.cpp

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x,y,id;
};

struct ClosestPair {
    int dist2, p1, p2;
    vector<Point> bigBuffer;
    ClosestPair() : dist2(numeric_limits<int>::max()), p1(-1), p2(-1) {}

    void upd(Point& l, Point& r) {
        int d2 = pow(l.x - r.x, 2) + pow(l.y - r.y, 2);
        if (d2 < dist2) {
            dist2 = d2;
            p1 = l.id;
            p2 = r.id;
        } 
    }

    void run(vector<Point>& points, int l, int r) {
        if (bigBuffer.size() == 0)
            bigBuffer.resize(points.size());

        if (r-l <= 3) {
            for (int i = l; i <= r; ++i)
                for (int j = i + 1; j <= r; ++j)
                    upd(points[i], points[j]);
            sort(points.begin()+l, points.begin() + r + 1, [](const Point& l, const Point& r) -> bool { return l.y < r.y; });
            return;
        }
        int m = l + (r - l)/2;
        int mx = points[m].x;
        run(points, l, m);
        run(points, m+1, r);
        merge(points.begin() + l, points.begin() + m + 1, points.begin() + m + 1, points.begin() + r + 1, bigBuffer.begin(),
                [](const Point& l, const Point& r) -> bool { return l.y < r.y; });

        copy(bigBuffer.begin(), bigBuffer.begin() + r - l + 1, points.begin() + l);
        int tsz = 0;
        for (int i = l; i <= r; ++i) {
            if (pow(points[i].x - mx, 2) < dist2) {
                for (int j = tsz - 1; j >= 0 && pow(points[i].y - bigBuffer[j].y, 2) < dist2; --j)
                    upd(points[i], bigBuffer[j]);
                bigBuffer[tsz] = points[i];
                ++tsz;
            }
        }
    }

};
int main(int, char**) {
    ClosestPair cp;

    vector<Point> points = { {1,1,0}, {1,3,1}, {2,4,2}, {2,8,3}, {3,2,4} };
    sort(points.begin(), points.end(), [](const Point& l, const Point& r) -> bool { return l.x < r.x; });

    cp.run(points, 0, points.size()-1);
    cout << cp.dist2 << " " << cp.p1 << " " << cp.p2 << "\n";
    return 0;
}