Cod sursa(job #1567423)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 13 ianuarie 2016 11:06:26
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
pair<ll ,ll> ve[100005];
int si[100005],di[100005];
bool cm2(int i,int j)
{
    if(ve[i].second!=ve[j].second)
      return ve[i].second<ve[j].second;
    return ve[i].first<ve[j].first;
}
long long dist(int i,int j)
{
    return (ve[i].first-ve[j].first)*(ve[i].first-ve[j].first)+(ve[i].second-ve[j].second)*(ve[i].second-ve[j].second);
}
long long solve(int st,int dr)
{
            long long ans=-1,a2;
            int i,j,mi=(st+dr)/2,ls=0,ld=0,l;
    if(dr-st<=3)
    {
        for(i=st;i<=dr;i++)
            for(j=i+1;j<=dr;j++)
            if(dist(i,j)<ans || ans<0)
            ans=dist(i,j);
            return ans;
    }
        ans=min(solve(st,mi),solve(mi+1,dr));
        for(i=st;i<=dr;i++)
            if(i<=mi)
        {
            ls++;
            si[ls]=i;
        }
        else
        {
            ld++;
            di[ld]=i;
        }
        sort(si+1,si+ls+1,cm2);
        sort(di+1,di+ld+1,cm2);
        l=1;
        a2=sqrt(ans);
        for(i=1;i<=ls;i++)
            for(j=l;j<=ld;j++)
            {
            if(ve[si[i]].first<ve[di[j]].first-a2)
                break;
                if(ve[si[i]].first>ve[di[j]].first+a2)
                    l=j+1;
                    ans=min(ans,dist(si[i],di[j]));
            }
            for(i=1;i<ls;i++)
                ans=min(ans,dist(si[i],si[i+1]));
            for(i=1;i<ld;i++)
                ans=min(ans,dist(di[i],di[i+1]));
            return ans;
}
int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    int n,i,j;
    long long ans;
    double af;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lld%lld",&ve[i].first,&ve[i].second);
    sort(ve+1,ve+n+1);
    ans=solve(1,n);
    af=sqrt(ans);
    printf("%lf\n",af);
    return 0;
}