Cod sursa(job #781409)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 24 august 2012 13:44:34
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
typedef struct w{long long x,y;}point;
point a[100001],aux[50001];

bool cmp(point a,point b){if (a.x==b.x) return(a.y<b.y); else return(a.x<b.x); }
bool cmp1(point a,point b){if (a.y==b.y) return(a.x<b.x); else return(a.y<b.y); }
long double abs(long double w){if (w>0) return(w); else return(-w); }
long double dist(point a, point b){ return(sqrt((long double)(a.x-b.x)*(a.x-b.x)+(long double)(a.y-b.y)*(a.y-b.y))); }
long double min(long double a,long double b){if (a<b) return(a); else return(b); }

long double solution(int l, int r){
       if (l==r) return(1000000000);
        else if (l==r-1) return(dist(a[l],a[r]));
       int mid=(l+r)/2;
       long double sl=solution(l,mid);
       long double sr=solution(mid+1,r);
       long double s=min(sl,sr);
        int nr=0,i,j;
       for (i=l; i<=r; ++i)
        if (abs(a[i].x-mid)<=s) {++nr; aux[nr]=a[i]; }
       sort(aux+1,aux+nr+1,cmp1);
        for (i=1; i<nr; ++i){
            int lim;
            if (i+7<=nr) lim=i+7; else lim=nr;
             for (j=i+1; j<=lim; ++j) s=min(s,dist(aux[i],aux[j]));
            }
       return(s);
}

int main(void){
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    int i,n; fin>>n;
    for (i=1; i<=n; ++i) fin>>a[i].x>>a[i].y;
     sort(a+1,a+n+1,cmp);
    fout<<setprecision(20)<<solution(1,n);
  return(0);
}