Cod sursa(job #1527976)

Utilizator 2chainzTauheed Epps 2chainz Data 18 noiembrie 2015 21:54:34
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<fstream>
#include<algorithm>
#define x first
#define y second
#define Point pair<double,double>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
const int Nmax = 100001;
Point v[Nmax],ax[Nmax],q[20];
int N,K,R;
double dist(Point A,Point B){return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y) );}
struct cmp{inline bool operator ()(const Point &A,const Point &B)const{return A.y<B.y;}};
double cmap(int st,int dr){
    if(dr-st <= 2){
        double sol=1e100;
        for(int i=st;i<=dr;i++)
        for(int j=i+1;j<=dr;j++) sol=min(sol,dist(v[i],v[j]));
        sort(v+st,v+dr+1,cmp());
        return sol;
    }
    else{
        int mij=(st+dr)/2;
        double MIJ=v[mij].x;
        double s1=cmap(st,mij);
        double s2=cmap(mij+1,dr);
        double ss=min(s1,s2),S=ss;
        int i=st,j=mij+1;
        K=0;
        while(i<=mij && j<=dr){
            if(v[i].y<v[j].y) ax[++K]=v[i++];
            else ax[++K]=v[j++];
        }
        while(i<=mij)ax[++K]=v[i++];
        while(j<=dr)ax[++K]=v[j++];
        R=0;
        for(int i=st;i<=dr;i++){
            v[i]=ax[i-st+1];
            if(abs(v[i].x-MIJ)<=ss){
                for(int j=0;j<min(R,12);j++) S=min(S,dist(v[i],q[j]));
                q[R%12]=v[i];
                R++;
            }
        }
        return S;
    }
}
int main(){
    in>>N;
    for(int i=1;i<=N;i++) in>>v[i].x>>v[i].y;
    sort(v+1,v+N+1);
    out.precision(8);
    out<<fixed<<cmap(1,N)<<'\n';
    return 0;
}