What is the complexity of this code ?

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

The problem

Given $$$n$$$ points $$$(x_1, y_1),\ (x_2, y_2),\dots, (x_n, y_n)$$$

Find the minimum distance between 2 pair of points.

The problem: SPOJ

The constraint

$$$2 \leq n \leq 50000$$$
$$$x_i, y_i \leq 10^6$$$

My question

I was solving a problem that need to find the minimum distance between two points. I tried to bruteforce then cde an divide and conquer algorithm. But then I modified the bruteforce by adding some branch-and-bound to ignore not-optimal cases. For somehow my code get AC and seems to run fast while I thought it will be slow with the complexity of $$$O(n^2)$$$ with small constant.

I dont really sure about the complexity, can some one help me to calculate it ?

My main part

int main()
{
    int n;
    cin >> n;

    /// Input points
    vector<point> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i].x >> a[i].y;

    /// Sorted by minimum(y) then minimum(x)
    set<point, cmp_y> S;
    set<point, cmp_y>::iterator it;

    double CMD = 1e9; /// Current Minimum Distance
    ll CMSD = 1e18;   /// Current Minimum Squared Distance
    for (int i = 0; i < n; ++i)
    {
        point lower(a[i].x, a[i].y - CMD); /// Lower   will give longer distance
        point upper(a[i].x, a[i].y + CMD); /// Shorter will give longer distance
        for (it = S.lower_bound(lower); it != S.end() && sorty(*it, upper); ++it) 
        {
            int dx = abs(a[i].x - it->x);
            int dy = abs(a[i].y - it->y); 
            if (dx >= CMD && dy >= CMD) it = S.erase(it); /// This point is not optimal, remove it
            if (dx >= CMD || dy >= CMD) continue;         /// Distance >= CMD -> Skip
         
            ll CD = 1LL * dx * dx + 1LL * dy * dy; /// Current Distance
            minimie(CMSD, CD);                     /// Update Distance
        }
        S.insert(a[i]);   /// Add new point
        CMD = sqrt(CMSD); /// Recalculate Minimum Distance
    }

    cout << CMD; /// Answer
    return 0;
}

My full code

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <set>

using namespace std;

#define all(x) (x).begin(), (x).end()

char __;
template <typename _T_>
void getSigned(_T_ &_n_) /// For inputing many numbers
{
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
    bool sign(__ == '-');
    if (sign) __ = getchar();

    _n_ = __ - '0';
    while (__ = getchar(), __ >= '0' && __ <= '9')
        _n_ = 10 * _n_ + __ - '0';
    
    if (sign) _n_ = -_n_;
}

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

struct point /// (x, y) cordinate
{
    int x, y;
    point(int x = 0, int y = 0)
    : x(x), y(y) {}
};

bool sortx (const point &a, const point &b) { return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y); }
bool sorty (const point &a, const point &b) { return (a.y != b.y) ? (a.y < b.y) : (a.x < b.x); }
struct cmp_x { bool operator() (const point &a, const point &b) { return sortx(a, b); } };
struct cmp_y { bool operator() (const point &a, const point &b) { return sorty(a, b); } };
typedef long long ll;
int main()
{
    int n;
    cin >> n;

    /// Input points
    vector<point> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i].x >> a[i].y;

    /// Sorted by minimum(y) then minimum(x)
    set<point, cmp_y> S;
    set<point, cmp_y>::iterator it;

    double CMD = 1e9; /// Current Minimum Distance
    ll CMSD = 1e18;   /// Current Minimum Squared Distance
    for (int i = 0; i < n; ++i)
    {
        point lower(a[i].x, a[i].y - CMD); /// Lower   will give longer distance
        point upper(a[i].x, a[i].y + CMD); /// Shorter will give longer distance
        for (it = S.lower_bound(lower); it != S.end() && sorty(*it, upper); ++it) 
        {
            int dx = abs(a[i].x - it->x);
            int dy = abs(a[i].y - it->y); 
            if (dx >= CMD && dy >= CMD) it = S.erase(it); /// This point is not optimal, remove it
            if (dx >= CMD || dy >= CMD) continue;         /// Distance >= CMD -> Skip
         
            ll CD = 1LL * dx * dx + 1LL * dy * dy; /// Current Distance
            minimie(CMSD, CD);                     /// Update Distance
        }
        S.insert(a[i]);   /// Add new point
        CMD = sqrt(CMSD); /// Recalculate Minimum Distance
    }

    cout << CMD; /// Answer
    return 0;
}

SPyofgame's blog

The problem

The constraint

My question