Cod sursa(job #2834912)

Utilizator BalasaRaduBalasa Radu BalasaRadu Data 17 ianuarie 2022 20:46:25
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const int dim=100009;

struct punct{
    int x,y;
    bool operator <(const punct &other) const
    {
        if(y==other.y){
            return x<other.x;
        }
        return y<other.y;
    }
};

set<punct>s;
punct v[dim];

bool cmp(punct a, punct b){
    if(a.x==b.x){
        return a.y<b.y;
    }
    return a.x<b.x;
}

double dist(punct a,punct b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

signed main(){
    int n;
        fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp);
    double hmin=dist(v[1],v[2]);
    int j=1;
    for(int i=1;i<=n;i++){
        int d=ceil(hmin+1);
        while(v[i].x-v[j].x>=d){
            s.erase(v[j]);
            j++;
        }
        auto it1=s.lower_bound({v[i].x,v[i].y-d});
        auto it2=s.upper_bound({v[i].x,v[i].y+d});
        for(auto it=it1;it!=it2;it++){
            hmin=min(hmin,dist(v[i],*it));
        }
        s.insert(v[i]);
    }
        fout<<fixed<<setprecision(8)<<hmin;
}