Cod sursa(job #1412639)

Utilizator UVS_Miriam_Piro_DianaFrumoasele si Bestialul UVS_Miriam_Piro_Diana Data 1 aprilie 2015 13:25:29
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
const double INF = 1e100;
const int Nmax = 100001;
struct pnt{
    int x,y;
    bool operator < (const pnt &z) const {return x<z.x;}
} v[Nmax],a[Nmax],tem[Nmax];
int N;
bool cmp(pnt a,pnt b){return a.y<b.y;}
double l(pnt &a,pnt &b){return double(a.x-b.x)*(a.x-b.x) + double(a.y-b.y)*(a.y-b.y);}
double absol(double a){if(a>0) return a;return -a;}
void pat(pnt &ch,double &sp,double &S,vector<pnt> &V,double &NS){
    if(absol(ch.x-sp)<=S){
        for(vector<pnt>::iterator it=V.begin();it!=V.end();++it){
            NS=min(NS,l(ch,*it));
        }
        V.push_back(ch);
        if(V.size()>10) V.pop_back();
    }
}
double dist(int st,int dr){
    if(dr-st+1<=5){
        double d=INF;
        for(int i=st;i<=dr;i++){
            for(int j=i+1;j<=dr;j++) d=min(d,l(v[i],v[j]));
            a[i]=v[i];
        }
        sort(a+st,a+dr+1,cmp);
        return d;
    }
    int mij=(st+dr)>>1,i=st,j=mij+1,sz=0;
    double sp=(v[mij].x+v[mij+1].x)/2.;
    double S=min(dist(st,mij),dist(mij+1,dr)),NS=INF;
    vector<pnt> V; pnt ch;
    while(i<=mij && j<=dr){
        if(a[i].y < a[j].y) ch=a[i++];
        else ch=a[j++];
        pat(ch,sp,S,V,NS);
        tem[++sz]=ch;
    }
    while(i<=mij) ch=a[i++],pat(ch,sp,S,V,NS),tem[++sz]=ch;
    while(j<=dr) ch=a[j++],pat(ch,sp,S,V,NS),tem[++sz]=ch;
    for(i=1;i<=sz;i++) a[st+i-1]=tem[i];
    return min(S,NS);
}
int main(){
    in>>N;
    for(int i=1;i<=N;i++) in>>v[i].x>>v[i].y;
    sort(v+1,v+N+1);
    double ans=dist(1,N);
    ans=sqrt(ans);
    out.precision(8);
    out<<fixed<<ans<<'\n';
    return 0;
}