Cod sursa(job #1498566)

Utilizator 2chainzTauheed Epps 2chainz Data 8 octombrie 2015 19:22:43
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
const int Nmax = 100001;
struct pnt{
    double x,y;
    bool operator < (const pnt &t) const {
        if(y==t.y) return x<t.x;
        return y<t.y;
    }
};
pnt v[Nmax],au[Nmax];
int N;
struct cmpx{inline bool operator () (const pnt &A,const pnt &B) const {return A.x < B.x;}};
struct cmpy{inline bool operator () (const pnt &A,const pnt &B) const {return A.y < B.y;}};
double dist(pnt A,pnt B){return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);}
double calc(int st,int dr){
    if(dr-st<=2){
        double ans=1e20;
        for(int i=st;i<=dr;i++) for(int j=i+1;j<=dr;j++) ans=min(ans,dist(v[i],v[j]));
        sort(v+st,v+dr+1,cmpy());
        return sqrt(ans);
    }
    else{
        int mij=(st+dr)/2;
        double s1 = calc(st,mij);
        double s2 = calc(mij+1,dr);
        double S=min(s1,s2);
        double sol=S;

        int stt=1,drr=0;
        for(int i=st;i<=dr;i++){
            if(abs(v[i].x-v[mij].x) <= S){
                au[++drr]=v[i];
                if(drr-stt > 12) stt++;
                for(int j=stt;j<drr;j++){
                    sol=min(sol,dist(au[j],au[drr]));
                }
            }
        }

        int i=st,j=mij+1,k=0;
        while(i<=mij && j<=dr){
            if(v[i] < v[j]) au[++k]=v[i++];
            else au[++k]=v[j++];
        }
        while(i<=mij) au[++k]=v[i++];
        while(j<=dr) au[++k]=v[j++];
        for(i=1;i<=k;i++) v[st+i-1]=au[i];

        return sol;
    }
}
int main(){
    in>>N;
    for(int i=1;i<=N;i++) in>>v[i].x>>v[i].y;
    sort(v+1,v+N+1,cmpx());
    double a = calc(1,N);
    out.precision(7);
    out<<fixed<<a<<'\n';
    return 0;
}