Cod sursa(job #2683097)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 10 decembrie 2020 14:52:42
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const ll NMAX = 100005;
const ll INF = 1000000000000000001;
pair <ll,ll> a[NMAX],b[NMAX],c[NMAX];
ll n;
ll Abs(ll x){
    if(x<0) return -x;
    return x;
}
ll dist(pair<ll,ll> x,pair<ll,ll> y){
    return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second);
}
ll solve(ll st,ll dr){
    if(st>=dr) return INF;
    if(dr-st+1==2){
        if(b[st+1]<b[st]){
            pair<ll,ll> aux;
            aux=b[st+1];
            b[st+1]=b[st];
            b[st]=aux;
        }
        return dist(a[st],a[st+1]);
    }
    ll mij=(st+dr)/2;
    ll d=min(solve(st,mij),solve(mij+1,dr));
    ll i=st,j=mij+1,m=0;
    while(i<=mij and j<=dr){
        if(b[i]<=b[j]){
            c[++m]=b[i];
            i++;
        }
        else{
            c[++m]=b[j];
            j++;
        }
    }
    while(i<=mij){
        c[++m]=b[i];
        i++;
    }
    while(j<=dr){
        c[++m]=b[j];
        j++;
    }
    ll m2=0;
    for(ll i=st;i<=dr;i++){
        if(Abs(b[i].second-a[mij].first)<=d)
            c[++m2]=b[i];
    }
    for(ll i=1;i<=m2;i++)
        for(ll j=i+1;j<=m2 and j<=i+7;j++)
            d=min(d,dist(c[i],c[j]));
    return d;
}
int main()
{
    fin >> n;
    for(ll i=1;i<=n;i++) fin >> a[i].first >> a[i].second;
    sort(a+1,a+n+1);
    for(ll i=1;i<=n;i++){
        b[i].first=a[i].second;
        b[i].second=a[i].first;
    }
    fout << setprecision(6) << fixed << sqrt(solve(1,n));
    return 0;
}