Cod sursa(job #2618410)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 24 mai 2020 20:28:16
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
typedef pair<int,int> p;
p v[100005];
long double dist(p a,p b)
{
    return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
long double divide(int a, int b)
{
    long double Min = INT_MAX*1.0;
    if(b-a+1<=3)
    {
        for(int i=a;i<=b;i++)
        {
            for(int j=i+1;j<=b;j++)
            {
                if(dist(v[i],v[j])<Min)
                {
                    Min=dist(v[i],v[j]);
                }
            }
        }
        return Min;
    }
    int mij=(a+b)/2;
    Min=min(divide(a,mij),divide(mij+1,b));
    vector <p> points;
    for(int i=a;i<=b;i++)
    {
        if(abs(v[i].x-v[mij].x)<=Min && abs(v[i].y-v[mij].y)<=Min)
        {
            points.push_back(v[i]);
        }
    }
    for(int i=0;i<=points.size();i++)
    {
        int lim=i+8;
        if(i+8>points.size())
            lim=points.size();
        for(int j=i+1;j<lim;j++)
        {
            Min=min(Min,dist(points[i],points[j]));
        }
    }
    return Min;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>v[i].first>>v[i].second;
    }
    sort(v+1,v+n+1);
    g<<fixed<<setprecision(6);
    g<<divide(1,n)<<'\n';
    return 0;
}