Cod sursa(job #1567013)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 12 ianuarie 2016 21:05:00
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 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 cmp(pair<ll,ll> a1,pair<ll,ll> a2)
{
    if(a1.first!=a2.first)
    return a1.first<a2.first;
    return a1.second<a2.second;
}
bool cm2(pair<ll,ll> a1,pair<ll,ll> a2)
{
    if(a1.second!=a2.second)
      return a1.second<a2.second;
    return a1.first<a2.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;
    }
        sort(ve+st,ve+dr+1,cmp);
        ans=min(solve(st,mi),solve(mi+1,dr));
        sort(ve+st,ve+dr+1,cm2);
        for(i=st;i<=dr;i++)
            if(ve[i].second<=ve[mi].second)
        {
            ls++;
            si[ls]=i;
        }
        else
        {
            ld++;
            di[ld]=i;
        }
        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);
    ans=solve(1,n);
    af=sqrt(ans);
    printf("%lf\n",af);
    return 0;
}