Cod sursa(job #2490210)

Utilizator lucianistratiIstrati Lucian lucianistrati Data 9 noiembrie 2019 21:56:44
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
#define pb push_back
#define uii unsigned int
#define ll long long
using namespace std;
 
vector <pair<ll,ll> > v;
ll dist(pair <ll,ll> a,pair<ll,ll> b)
{
    ll p1x=a.first;
    ll p1y=a.second;
    ll p2x=b.first;
    ll p2y=b.second;
    return ((p1x-p2x)*(p1x-p2x)+(p1y-p2y)*(p1y-p2y));
}
ll divideEtImpera(ll st,ll dr)
{
    ll mij,minL,minR;
    ll d;
    if(dr-st<=3)
    {
        ll minim=1e18;
        uii i,j;
        for(i=st;i<=dr;i++)
        {
            for(j=i+1;j<=dr;j++)
            {
                minim=min(minim,dist(v[i],v[j]));
            }
        }
        return minim;
    }
    uii i,j;
    mij=st+(dr-st)/2;
    d=min(divideEtImpera(st,mij),divideEtImpera(mij+1,dr));
    vector  < pair<ll,ll> > new_v;
    for(i=st;i<=dr;i++)
    {
        if(abs(v[mij].first-v[i].first)<d)
        {
            new_v.push_back({v[i].second,v[i].first});
        }
    }
    sort(new_v.begin(),new_v.end());
    for(i=0;i<new_v.size();i++)
    {
        for(j=i+1;j<new_v.size() &&  j < i + 8;j++)
        {
                ll new_d;
                new_d=dist(new_v[i],new_v[j]);
                if(new_d<d)
                {
                    d=new_d;
                }
            }
    }
    return d;
}
int main()
{
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    int n,i,j;
    ll a,b;
    double f;
    double min=999999999;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        v.pb({a,b});
    }
    ll dist_best=1e9;
    sort(v.begin(),v.end());
    dist_best=divideEtImpera(0,n-1);
    fout<<fixed<<setprecision(6)<<sqrt((double)dist_best);
    fin.close();
    fout.close();
    return 0;
}