Cod sursa(job #2617903)

Utilizator BogdanFarcasBogdan Farcas BogdanFarcas Data 23 mai 2020 12:25:46
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const int N=100001;
const int MAX=2000000001;
pair <int,int>p[N];
pair <int,int>a[N];
int n;

double dist(int x1,int y1,int x2,int y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double divide(int st,int dr)
{
    if(dr-st<=2)
    {
        double d=MAX;
        for(int i=st;i<dr;i++)
        {
            for(int j=i+1;j<=dr;j++)
            {
                d=min(d,dist(p[i].first,p[i].second,p[j].first,p[j].second));
            }
        }
        return d;
    }
    int mij=(st+dr)/2;
    double dst=divide(st,mij);
    double ddr=divide(mij+1,dr);
    double dmin=min(dst,ddr);
    double ds=(p[st].first+p[dr].first)/2;
    int top=0;
    for(int i=st;i<=dr;i++)
    {
        if(p[i].first>=ds-dmin&&p[i].first<=ds+dmin)
        {
            a[++top]=p[i];
        }
    }
    for(int i=1;i<top;i++)
    {
        for(int j=i+1;j<=top;j++)
        {
            dmin=min(dmin,dist(a[i].first,a[i].second,a[j].first,a[j].second));
        }
    }
    return dmin;
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>p[i].first>>p[i].second;
    }
    sort(p+1,p+n+1);
    fout<<fixed<<setprecision(6)<<divide(1,n);
    return 0;
}