Cod sursa(job #978950)

Utilizator andrettiAndretti Naiden andretti Data 30 iulie 2013 16:22:06
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#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];
int n,ny;
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 (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

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

    if(right-left+1<=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]));
        return pair_min;
    }

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

    int i=mid,j=mid+1; ny=0;
    while(dist(px[mid],px[i])<pair_min && i>=left) py[++ny]=px[i++];
    while(dist(px[mid],px[j])<pair_min && j<=right) py[++ny]=px[j++];
    sort(py+1,py+ny+1,cmpy);

    for(i=1;i<ny;i++)
     for(j=i+1;j<=ny;j++)
      pair_min=min(pair_min,dist(py[i],py[j]));

    return pair_min;
}

void solve()
{
    sort(px+1,px+n+1,cmpx);
    sol=det_pair(1,n);
    printf("%.6lf",sqrt(sol));
}

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

    read();
    solve();

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