Cod sursa(job #1617472)

Utilizator avaspAva Spataru avasp Data 27 februarie 2016 14:14:41
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
struct puncte{int x, y;};
puncte v[100001];
int n;
vector<puncte>s;

bool cmp(const puncte A, const puncte B){
    return A.x<B.x;
}

long long minim(long long nr1,long long nr2){
    if(nr1<nr2)
        return nr1;
    return nr2;
}

long long divi(int l1,int l2){
    if(l1==l2-1||l2==l1-1)
        return 1LL*(1LL*(v[l1].x-v[l2].x)*(v[l1].x-v[l2].x) +1LL*(v[l1].y-v[l2].y)*(v[l1].y-v[l2].y) );
    if(l1==l2)
        return 1LL*4*1000000000000000001;
    return minim(divi(l1,(l1+l2)/2) , divi( (l1+l2)/2 +1, l2) );
}


int main(){
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&v[i].x,&v[i].y);
    }
    sort(v+1,v+n+1,cmp);
    long long d=minim( divi(1,n/2) , divi(n/2+1,n) );
    for(int i=1;i<=n;i++){
        if((v[n/2].x-v[i].x)*(v[n/2].x-v[i].x) <d)
            s.push_back(v[i]);
    }

    for(int i=0;i<s.size();i++)
        for(int j=i+1;j<s.size();j++){
            int l1,l2;
            l1=i;l2=j;
            if( (1LL*(v[l1].x-v[l2].x)*(v[l1].x-v[l2].x) +1LL*(v[l1].y-v[l2].y)*(v[l1].y-v[l2].y) ) < d)
                d=1LL*(1LL*(v[l1].x-v[l2].x)*(v[l1].x-v[l2].x) +1LL*(v[l1].y-v[l2].y)*(v[l1].y-v[l2].y) );
        }
    printf("%lf",sqrt(d));
    return 0;
}