Cod sursa(job #3239682)

Utilizator lucriLuchian Cristian lucri Data 7 august 2024 12:24:56
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
long long nr,n,x,y,ans=8000000000000000010;
struct punct{long long x,y;}p1,p2;
vector<punct>a,c;
inline static bool comp2(punct a,punct b)
{
    return a.x<b.x;
}
inline static bool comp(punct a,punct b)
{
    return a.y<b.y;
}
inline static long long distance(punct a,punct b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline static long long divide(long long b,long long e)
{
    if(b==e)
        return a[b].x;
    long long l=divide(b,(b+e)/2);
    long long nl=divide((b+e)/2+1,e);
    merge(a.begin()+b,a.begin()+(b+e)/2+1,a.begin()+(b+e)/2+1,a.begin()+e+1,c.begin(),comp);
    for(long long i=b;i<=e;++i)
        a[i]=c[i-b];
    nr=0;
    for(long long i=b;i<=e;++i)
    {
        if((l-a[i].x)*(l-a[i].x)<=ans)
        {
            c[nr]=a[i];
            ++nr;
        }
    }
    for(long long i=0;i<nr;++i)
    {
        for(long long j=i-1;j>=0&&(c[i].y-c[j].y)*(c[i].y-c[j].y)<ans;--j)
        {
            if(ans>distance(c[i],c[j]))
            {
                ans=distance(c[i],c[j]);
                p1=c[i];
                p2=c[j];
            }
        }
    }
    return nl;
}
int main()
{
    in>>n;
    c.resize(n);
    for(long long i=1;i<=n;++i)
    {
        in>>x>>y;
        a.push_back({x,y});
    }
    sort(a.begin(),a.end(),comp2);
    divide(0,n-1);
    out<<fixed<<setprecision(10)<<sqrt(1.0*ans);
    return 0;
}