Cod sursa(job #2668374)

Utilizator metallidethantralayerIon Cojocaru metallidethantralayer Data 4 noiembrie 2020 20:22:43
Problema Cele mai apropiate puncte din plan Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;
struct Punct
{
    double x,y;
} v[100005],v1[100005],v2[100005];
int64_t n;
int64_t Distanta(const Punct a,const Punct b)
{
    return (a.x-b.x)*(a.x-b.x)+(b.y-a.y)*(b.y-a.y);
}
bool Compare(const Punct &a,const Punct &b)
{
    return a.y<b.y;
}
bool Compare1(const Punct &a,const Punct &b)
{
    return a.x<b.y;
}
int64_t Fct(int st,int dr)
{
    if(dr-st<=1)
        return 4e18;
    else if(dr-st==2)
    {
        if(v1[st].y>v1[st+1].y)
            swap(v1[st],v1[st+1]);
        return Distanta(v1[st],v1[st+1]);
    }
    else
    {
        int mi=(st+dr)>>1;
        int64_t mn=min(Fct(st,mi),Fct(mi,dr));
        sort(v1+st,v1+dr,Compare);
        int64_t h=0;
        for(int i=st; i<dr; i++)
            if(abs(v1[i].x-v[mi].x)<=mn)
                v2[++h]=v1[i];
        for(int i=1; i<h; i++)
            for(int j=i+1; j<h&&j-i<8; j++)
                mn=min(mn,Distanta(v2[i],v2[j]));
        return mn;
    }
}
int main()
{
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    f>>n;
    for(int i=0; i<n; i++)
        f>>v[i].x>>v[i].y,v1[i]=v[i];
    sort(v,v+n,Compare1);
    g<<fixed<<setprecision(6)<<sqrt(Fct(1,n));
    return 0;
}