Cod sursa(job #2397870)

Utilizator DimaTCDima Trubca DimaTC Data 4 aprilie 2019 20:29:30
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include<bits/stdc++.h>
#define pdd pair<double,double>
#define x first
#define y second
#define N 100030
#define double long double
using namespace std;

int n,p;
pdd a[N];
double d=1e13;
struct cmp {
    bool operator()(int l, int r) {
        return a[l].y<a[r].y;
    }
};
set<int,cmp>S;

double dist(pdd A, pdd B) {
    return (sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y)));
}

int main() {
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");
    cin>>n;
    for (int i=1; i<=n; ++i) cin>>a[i].x>>a[i].y;
    sort(a+1,a+1+n); p=1; S.insert(1);
    for (int i=2; i<=n; ++i) {
        while (a[i].x-a[p].x>d) {
            S.erase(p); ++p;
        }
        a[0].y=a[i].y-d;
        auto it=S.lower_bound(0);
        for (auto it=S.lower_bound(0); it!=S.end() && abs(a[*it].y-a[i].y)<=d; ++it) {
            double d2=dist(a[*it],a[i]);
            if (d2<d) d=d2;
        }
        S.insert(i);
    }

    cout<<fixed<<setprecision(10)<<d;

    return 0;
}