Cod sursa(job #1713593)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 6 iunie 2016 00:04:06
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
#define MAXN 100010
#define INF (1LL<<61)
using namespace std;
pair<int,int> v[MAXN],temp[MAXN];
long long Distance(pair<int,int> a,pair<int,int> b){
    return (long long)(a.first-b.first)*(a.first-b.first)+(long long)(a.second-b.second)*(a.second-b.second);
}
long long minimum(long long a,long long b){
    if(a<b)
        return a;
    return b;
}
long long Divide(int left,int right){
    int middle=(left+right)/2,i,j,k,current=0;
    long long answer;
    if(left>=right)
        return INF;
    if(left+1==right){
        if(v[left].second>v[right].second||(v[left].second==v[right].second&&v[left].first>v[right].first))
            swap(v[left],v[right]);
        return Distance(v[left],v[right]);
    }
    answer=minimum(Divide(left,middle),Divide(middle+1,right));
    i=left;
    j=middle+1;
    k=0;
    while(i<=middle&&j<=right)
        if(v[i].second>v[j].second||(v[i].second==v[j].second&&v[i].first>v[j].first)){
            k++;
            temp[k]=v[j];
            j++;
        }
        else{
            k++;
            temp[k]=v[i];
            i++;
        }
    while(i<=middle){
        k++;
        temp[k]=v[i];
        i++;
    }
    while(j<=right){
        k++;
        temp[k]=v[j];
        j++;
    }
    for(i=left;i<=right;i++)
        v[i]=temp[i-left+1];
    for(i=left;i<=right;i++)
        if((long long)(v[i].first-v[middle].first)*(v[i].first-v[middle].first)<=answer){
            current++;
            temp[current]=v[i];
        }
    for(i=1;i<current;i++)
        for(j=i+1;j<=current&&(long long)(temp[j].second-temp[i].second)*(temp[j].second-temp[i].second)<=answer;j++)
            answer=minimum(answer,Distance(temp[i],temp[j]));
    return answer;

}
int main(){
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i].first,&v[i].second);
    sort(v+1,v+n+1);
    printf("%f",sqrt(Divide(1,n)));
    return 0;
}