Cod sursa(job #1419353)

Utilizator livliviLivia Magureanu livlivi Data 15 aprilie 2015 13:56:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#define N 100000
#define MULT 9223372036854775807
using namespace std;

struct mazi{
    long long x,y;
};

mazi v[N+1];
mazi aux[N+1];
long long dmin;


long long dist(mazi a,mazi b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}


long long min(long long a,long long b){
    if (a<b) return a;
    return b;
}


void merge(int l1,int r1,int l2,int r2){
    int k=0;

    while(l1<=r1 &&l2<=r2){
        k++;

        if (v[l1].y<v[l2].y){
            aux[k]=v[l1];
            l1++;
        }
        else {
            aux[k]=v[l2];
            l2++;
        }
    }

    while(l1<=r1){
        k++;
        aux[k]=v[l1];
        l1++;
    }
    while(l2<=r2){
        k++;
        aux[k]=v[l2];
        l2++;
    }

    for(int i=r2;k>0;k--,i--)
        v[i]=aux[k];
}


void query(int begin,int end){
    int mid,i,j;
    long long d;

    if (begin>=end) return ;

    mid=(begin+end)/2;
    d=v[mid].x;

    query(begin,mid);
    query(mid+1,end);

    merge(begin,mid,mid+1,end);

    int k=0;
    for(i=begin;i<=end;i++)
        if ((v[i].x-d)*(v[i].x-d)<dmin){
            k++;
            aux[k]=v[i];
        }

    for(i=1;i<k;i++)
        for(j=i+1;j<=i+8 &&j<=k;j++)
            dmin=min(dmin,dist(aux[i],aux[j]));
}


bool meow(mazi a,mazi b){
    if (a.x<b.x) return true;
    if (a.x==b.x &&a.y<b.y) return true;
    return false;
}


int main(){
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    int n,i;

    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;

    sort(v+1,v+n+1,meow);
    dmin=MULT;

    query(1,n);

    //fout<<dmin;
    fout<<fixed<<setprecision(6)<<sqrt(1.0*dmin);

    fin.close();
    fout.close();
    return 0;
}