Cod sursa(job #978949)

Utilizator andrettiAndretti Naiden andretti Data 30 iulie 2013 16:15:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<vector>
#define pb push_back
#define maxn 100005
#define inf 1LL<<60
using namespace std;
typedef long long ll;

struct point{int x,y;} px[maxn],py[maxn],v[maxn];
int n,nv;
ll sol;

void read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&px[i].x,&px[i].y);
}

int cmpx(point a,point b)
{
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

int cmpy(point a,point b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}

ll dist(point a,point b)
{
    return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
}

ll det_pair(int left,int right)
{
    ll pair_min=inf;

    if(right-left<3)
    {
        for(int i=left;i<=right-1;i++)
         for(int j=i+1;j<=right;j++)
          pair_min=min(pair_min,dist(px[i],px[j]));
        sort(py+left,py+right+1,cmpy);
        return pair_min;
    }

    int mid=(left+right)/2;
    pair_min=min(det_pair(left,mid),det_pair(mid+1,right));

    merge(py+left,py+mid+1,py+mid+1,py+right+1,v+1,cmpy);
    memcpy(py+left,v+1,right-left+1);

    int i,j; nv=0;
    for(i=left;i<=right;i++)
     if(abs(px[mid].x-px[i].x)<=pair_min)
      v[++nv]=px[i];

    for(i=1;i<nv;i++)
     for(j=i+1;j<=nv && j-i<=7;j++)
      pair_min=min(pair_min,dist(v[i],v[j]));

    return pair_min;
}

void solve()
{
    sort(px+1,px+n+1,cmpx);
    for(int i=1;i<=n;i++) py[i]=px[i];
    printf("%lf",sqrt(det_pair(1,n)));
}

int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);

    read();
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}