Cod sursa(job #1900780)

Utilizator deliabiancasuciuSuciu delia deliabiancasuciu Data 3 martie 2017 16:27:49
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
struct pct
{
    long long x,y;
}p1,p2,p3,p4,pmij,v[1000005],aux[1000005];
bool comparex (const struct pct &p1, const struct pct &p2)
{
    return p1.x < p2.x;
}
bool comparey (const struct pct &p1,const struct pct &p2)
{
    return p1.y<p2.y;
}
int n,i,j,st,dr;
double dist ( struct pct p1, struct pct p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double bf(struct pct v[],int st,int dr)
{
    double dmin = 1000000; int i,j;
    for(i=st;i<dr;i++)
        for(j=i+1;j<=dr;j++)
            if(dist(v[i],v[j])<dmin)
                dmin = dist(v[i],v[j]);
    return dmin;
}
double mini (struct pct aux [], int nr, double dmin)
{
    double daux = 1000000; int i,j;
    sort(aux+1,aux+nr+1,comparey);
    for(i=1;i<nr;i++)
        for(j=i+1;j<=nr;j++)
            {
                if((aux[j].y-aux[i].y) <= daux && dist(aux[i],aux[j]) < daux)
                    daux = dist(aux[i],aux[j]);
            }
    return daux;
}
double rmin ( struct pct v[], int st,int dr )
{
    int mij; int i,j;
    double d1,d2,dmin,daux;
    if (dr-st < 3)
        return bf(v,st,dr);
    mij = st + (dr-st)/2;
    pmij = v[mij];
    d1 = rmin(v,st,mij);
    d2 = rmin(v,mij,dr);
    dmin = min(d1,d2);
    int nr = 0;
    for(i=st;i<=dr;i++)
        if(v[i].x<= pmij.x+dmin && v[i].x >= pmij.x-dmin)
            aux[++nr] = v[i];
    daux = mini(aux,nr,dmin);
    return min(dmin,daux);
}
int main()
{
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,comparex);
    /*for(i=1;i<=n;i++)
      out<<v[i].x<<" "<<v[i].y<<"\n";*/
    //out<<bf(v,1,n)<<"\n";
    out<<setprecision(6)<<fixed <<rmin(v,1,n);
    return 0;
}