Cod sursa(job #1985242)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 27 mai 2017 11:37:50
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include<bits/stdc++.h>
#define maxN 100005
using namespace std;
long long dist(int a,int b,int c,int d)
{
    return (1LL*(c-a))*(1LL*(c-a))+(1LL*(d-b))*(1LL*(d-b));
}
int n;
pair<int,int> v[maxN];
vector<int> x;
inline long long DivImp(int st,int dr)
{
    if((dr-st+1)<=3)
    {
        long long best=LLONG_MAX;
        for(int i=st;i<=dr;i++)
            for(int j=st;j<=dr;j++)
        {
            if(i!=j)
                best=min(best,dist(v[i].first,v[i].second,v[j].first,v[j].second));
        }
        return best;
    }
        else
    {
        int k,t;
        int mid=(st+dr)>>1;
        long long best=LLONG_MAX;
        best=min(DivImp(1,mid),DivImp(mid+1,dr));
      //  x.clear();
        for(int i=mid;i>=st && (v[mid].first-v[i].first)<=best;i--)
        {
         //   x.push_back(i);
            k=i;
        }
        for(int i=mid+1;i<=dr && (v[i].first-v[mid].first)<=best;i++)
        {
        //    x.push_back(i);
            t=i;
        }
        //for(int i=0;i<x.size();i++)
        //for(vector<int>::iterator it=x.begin();it!=x.end();it++)
        for(int i=k;i<=mid;i++)
        {
          //  int i=*it;
            for(int j=i+1;j<=t && (j-i)<=7;j++)
                best=min(best,dist(v[i].first,v[i].second,v[j].first,v[j].second));
        }
        return best;
    }
}
int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].first,&v[i].second);
    }
    sort(v+1,v+n+1);
    //printf("lld\n",DivImp(1,n));
    printf("%.6lf\n",sqrt((double)DivImp(1,n)));
    return 0;
}