Cod sursa(job #1567438)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 13 ianuarie 2016 11:35:35
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
pair<ll ,ll> ve[100005],v2[100005],v3[100005];
int si[100005],di[100005];
bool cm2(pair<ll, ll> i,pair<ll,ll> j)
{
    if(i.second!=j.second)
      return i.second<j.second;
    return i.first<j.first;
}
long long dist(pair<ll, ll> i,pair<ll,ll> j)
{
    return (i.first-j.first)*(i.first-j.first)+(i.second-j.second)*(i.second-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(ve[i],ve[j])<ans || ans<0)
            ans=dist(ve[i],ve[j]);
            for(i=st;i<=dr;i++)
            v2[i]=ve[i];
            sort(v2+st,v2+dr+1,cm2);
            return ans;
    }
        ans=min(solve(st,mi),solve(mi+1,dr));
        l=mi+1;
        a2=sqrt(ans);
        for(i=st;i<=mi;i++)
            for(j=l;j<=ld;j++)
            {
            if(v2[i].second<v2[j].second-a2)
                break;
                if(v2[i].second>v2[j].second+a2)
                    l=j+1;
                    ans=min(ans,dist(v2[i],v2[j]));
            }
            for(i=st;i<mi;i++)
                ans=min(ans,dist(v2[i],v2[i+1]));
            for(i=mi+1;i<dr;i++)
                ans=min(ans,dist(v2[i],v2[i+1]));
            i=st;j=mi+1;l=st-1;
            while(i<=mi || j<=dr)
            {
                if((cm2(v2[i],v2[j]) || j>dr) && i<=mi)
                {
                    l++;
                    v3[l]=v2[i];
                    i++;
                }
                else
                {
                    l++;
                    v3[l]=v2[j];
                    j++;
                }
            }
            for(i=st;i<=dr;i++)
            v2[i]=v3[i];
            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;
}