Cod sursa(job #1567056)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 12 ianuarie 2016 21:39:02
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
pair<ll ,ll> ve[100005];
int si[100005],di[100005],in[100005];
bool cmp(int i,int j)
{
    return ve[i]<ve[j];
}
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)
{
    long long x=ve[i].first-ve[j].first,y=ve[i].second-ve[j].second;
    return x*x+y*y;
}
long long mn(long long a,long long b)
{
    if(a<b)
        return a;
    return b;
}
long long solve(int st,int dr)
{
            long long ans=-1,a2;
            int i,j,mi=(st+dr)>>1,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=mn(solve(st,mi),solve(mi+1,dr));
        for(i=st;i<=dr;i++)
            if(ve[i].second<=ve[mi].second)
        {
            ls++;
            si[ls]=i;
        }
        else
        {
            ld++;
            di[ld]=i;
        }
        sort(si+1,si+ls+1,cm2);
        sort(di+1,di+ld+1,cm2);
        i=j=1;
        a2=sqrt(ans);
        while(i<=ls && j<=ld)
            {
                    ans=mn(ans,dist(si[i],di[j]));
                    if(si[i]>di[j])
                        j++;
                    else
                        i++;
            }
            for(i=1;i<ls;i++)
                ans=mn(ans,dist(si[i],si[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,af2;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld",&ve[i].first,&ve[i].second);
   in[i]=i;
    }
    sort(ve+1,ve+n+1);
    ans=solve(1,n);
    af2=ans;
    af=sqrt(af2);
    printf("%lf\n",af);
    return 0;
}