Cod sursa(job #1954386)

Utilizator vladttturcuman vlad vladtt Data 5 aprilie 2017 13:00:57
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <set>
#include <algorithm>

#define NMax 100010
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define int long long
struct Point{
int x,y;
bool operator< (const Point b) const
{
    return y < b.y;
}
};

Point a[NMax];

int n;

int dist(Point a, Point b)
{
    return (a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y);
}

bool XComparer(Point a,Point b)
{
    return a.x<b.x;
}

#undef int
int main()
{
    #define int long long
    fin>>n;
    int H = (1LL<<60);
    for(int i=1;i<=n;i++)
        fin>>a[i].x>>a[i].y;

    sort(a+1,a+1+n, XComparer);

    for(int i=2;i<=n;i++)
        H = min(H,dist(a[i],a[i-1]));

    multiset<Point> Set;
    multiset<Point>::iterator in, sf;

    int act=1;

    Point tmp;

    for(int i=1;i<=n;i++)
    {
        while(act <= n && (a[act].x - a[i].x) * (a[act].x - a[i].x)  < H )
        {
            Set.insert(a[act]);
            act++;
        }
        tmp.y = a[i].y - H + 1;
        in = Set.lower_bound(tmp);
        tmp.y = a[i].y + H - 1;
        sf = Set.upper_bound(tmp);


        while(in!= sf )
        {
            if(a[i].x != in->x || a[i].y != in->y)
                H = min(H,dist(a[i], *in ));

                in++;
        }


        in = Set.lower_bound(a[i]);
        Set.erase(in);


    }

    fout<<setprecision(6)<< fixed<< sqrt((double) H) <<'\n';


    return 0;
}