Cod sursa(job #1206642)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 10 iulie 2014 18:58:33
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
ifstream f("cmap.in");
ofstream o("cmap.out");
struct dat{
int x,y;
} v[100000];
int n, aux[1000000],y[10000000];
bool funct(dat i,dat j){
    return i.x>j.x;
}
bool funct1(int i,int j){
    return v[i].y>v[j].y;
}
long long int lung(dat p,dat q){
return 1LL*(p.x-q.x)*(p.x-q.x)+1LL*(p.y-q.y)*(p.y-q.y);
}
long long int devide(int l,int r){
   if(l+1==r)return lung(v[y[l]],v[y[r]]);
    if(l==r)return (1LL*1<<62);
    int m=(r+l)/2;
    long long int d = min(devide(m+1,r),devide(1,m));
    sort(y+l,y+r+1,funct1);
    int k=0;
    for(int i=l;i<=r;i++)
         if(abs(v[m].x-v[y[i]].x)<=d)aux[++k]=y[i];
    for(int i=1;i<=k-1;i++)
        for(int j=i+1;j<=k && j<=i+7;j++)
         d=min(d,lung(v[aux[i]],v[aux[j]]));
   return d;
}
int main(){
f>>n;
for(int i=1;i<=n;i++){
    f>>v[i].x>>v[i].y;
    y[i]=i;
}
sort(v+1,v+1+n,funct);
o<<setprecision(6);
o<<fixed;
o<<sqrt(devide(1,n));
}