Cod sursa(job #2545661)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 13 februarie 2020 13:01:53
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define NMAX (int)(1e5+4)
#define pb emplace_back
#define ft first
#define sd second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef pair <int, int> pairINT;
typedef long long ll;

int n;
double dmin;
pairINT p[NMAX];
queue <pairINT> active;
set <pairINT> s;
set <pairINT>::iterator it;

double dist(pairINT,pairINT);

int main(){
    fin>>n;
    for(int i=0,x,y;i<n;++i)
        fin>>p[i].ft>>p[i].sd;
    sort(p, p+n);
    dmin=dist(p[0], p[1]);
    active.push(p[0]);
    for(int i=1;i<n;++i){
        while(!active.empty() && p[i].ft - active.front().ft > dmin){
            active.pop();
            s.erase(s.find({active.front().sd, active.front().ft}));
        }
        active.push(p[i]);
        it=s.lower_bound({p[i].sd - dmin, p[i].ft});

        for(int i=0;i<8 && it != s.end();++i, ++it)
            dmin=min(dmin, dist(*it, p[i]));

        s.insert(p[i]);
    }
    fout<<fixed<<setprecision(6);
    fout<<sqrt(dmin);
    return 0;
}
double dist(pairINT A,pairINT B){
    return (1.0 * (B.ft - A.ft)) * (1.0 * (B.ft - A.ft)) +
            (1.0 * (B.sd - A.sd)) * (1.0 * (B.sd - A.sd));
}