Cod sursa(job #1303923)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 28 decembrie 2014 15:25:41
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#define DIM 100011
#define INF 2000000000
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
int sir[20];
pair<int,int> v[DIM];

inline double dist(int p,int u);
double divetimp(int p,int u);
int caut_bin1(int p,int u,int x,double q);
int caut_bin2(int p,int u,int x,double q);

int main(void){
    register int i,j;
    double sol;

    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].first>>v[i].second;
    sort(v+1,v+n+1);

    sol=divetimp(1,n);
    g<<setprecision(6)<<fixed<<sol;
    f.close();
    g.close();
    return 0;
}

double divetimp(int p,int u){
    int i,j,mid,p1,p2;
    double st,dr,q,minim=INF;
    if(u-p+1==2)
        return dist(p,u);
    if(u-p+1==3){
        for(i=p;i<u;i++)
            for(j=i+1;j<=u;j++)
                minim=min(minim,dist(i,j));
        return minim;
    }
    mid=(p+u)/2;
    st=divetimp(p,mid);
    dr=divetimp(mid+1,u);
    minim=min(st,dr);
    p1=caut_bin1(p,mid,v[mid].first,minim);
    p2=caut_bin2(mid+1,u,v[mid].first,minim);
    for(i=p1;i<p2;i++){
        for(j=i+1;j<=i+7 && j<=p2;j++){
            q=dist(i,j);
            if(q<minim) minim=q;
        }
    }
    return minim;
}

int caut_bin2(int p,int u,int x,double q){
    int mid;
    while(p<=u){
        mid=p+(u-p)/2;
        if(v[mid].first-x<=q)
            p=mid+1;
        else
            u=mid-1;
    }
    return u;
}

int caut_bin1(int p,int u,int x,double q){
    int mid;
    while(p<=u){
        mid=p+(u-p)/2;
        if(x-v[mid].first<=q)
            u=mid-1;
        else
            p=mid+1;
    }
    return p;
}

inline double dist(int p,int u){
    return sqrt((double)(v[u].first-v[p].first)*(v[u].first-v[p].first)+(double)(v[u].second-v[p].second)*(v[u].second-v[p].second));
}