[Spoj] Closest Point Pair

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Closest Point Pair
Source            : Spoj
Category          : Sweep Line Technique
Algorithm         : Sweep Line Technique
Verdict           : Accepted

#include <bits/stdc++.h>

using namespace std;
 
static const int MAXN = 1e5 + 5;
struct point
{
    double x, y;
    int p;
    point(double xx = 0, double yy = 0, int pp = 0)
    {
        x = xx;
        y = yy;
        p = pp;
    }
    bool operator<(const point &a) const
    {
        return x < a.x;
    }
};
point pt[MAXN];
struct yset
{
    double y;
    int pos;
    bool operator<(const yset &a) const
    {
        return y < a.y;
    }
};
double dist(point a, point b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
}
int main()
{
   // freopen("in.txt", "r", stdin);
 
    int n;
    //cin >> n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        //cin >> pt[i].x >> pt[i].y;
        scanf("%lf %lf", &pt[i].x, &pt[i].y);
        pt[i].p = i;
    }
        sort(pt, pt+n);
        set <yset> s;
        s.insert({pt[0].y, 0});
        double best = 1e14;
        int left = 0;
        int ansx, ansy;
        for (int i = 1; i < n; i++)
        {
            while (left < i && fabs(pt[left].x - pt[i].x) >= best)
            {
                s.erase({pt[left].y, left});
                left++;
            }
            auto p = s.lower_bound({pt[i].y - best, -1});  // -1 doesnot matter
            auto q = s.upper_bound({pt[i].y + best, n});
            while (p != q)
            {
                double dis = dist(pt[p->pos], pt[i]);
                if (best > dis)
                {
                    ansx = pt[p->pos].p;
                    ansy = pt[i].p;
                    best = dis;
                }
                p++;
            }
           s.insert({pt[i].y, i});
        }
        if (ansx > ansy)
            swap(ansx, ansy);
        printf("%d %d %.6lf\n", ansx, ansy, best);
        //cout << fixed << setprecision(6)
        //     << ansx << " " << ansy << " " << best;
        s.clear();
    return 0;
}