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;
}
