Cod sursa(job #2546645)

Utilizator RedPipperNastasa Stefan-Alexandru RedPipper Data 14 februarie 2020 12:41:11
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#define NMAX (int)(1e5+4)
#define ft first
#define sd second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long long ll;
typedef pair <ll, ll> pairINT;

ll n,lastX,dmin;
pairINT p[NMAX];
set <pairINT> sweep;

bool upd(int);
void pass(int);
ll dist(pairINT,pairINT);

int main(){
    fin>>n;
    for(int i=0;i<n;++i)
        fin>>p[i].ft>>p[i].sd;
    sort(p, p+n);
    sweep.insert({p[0].sd, p[0].ft});
    lastX=0;
    dmin=2e18;

    for(int i=1;i<n;++i){
        while(upd(i));
        sweep.insert({p[i].sd, p[i].ft});
        pass(i);
    }
    fout<<fixed<<setprecision(7)<<sqrt(1.0*dmin);
    return 0;
}
void pass(int k){
    ll sq=sqrt(1.0 * dmin);
    while(p[lastX].ft < p[k].ft - sq){
        sweep.erase({p[lastX].sd, p[lastX].ft});
        ++lastX;
    }
}
bool upd(int k){
    set <pairINT>::iterator it;
    bool ok=0;
    ll sq=sqrt(1.0 * dmin);
    ll temp = p[k].sd - sq;
    it=sweep.lower_bound({temp, 0LL});

    while(it != sweep.end()){
        temp=dist(p[k], {(*it).sd, (*it).ft});
        if(dmin > temp){
            dmin=temp;
            sq=sqrt(1.0 * dmin);
            ok=1;
        }
        if(temp > dmin)
            break;
        ++it;
    }
    return ok;
}
ll dist(pairINT A,pairINT B){
    return (B.ft - A.ft) * (B.ft - A.ft) +
            (B.sd - A.sd) * (B.sd - A.sd);
}