Cod sursa(job #2766783)

Utilizator stefanvoicaVoica Stefan stefanvoica Data 3 august 2021 12:21:31
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include<bits/stdc++.h>
#define dim 100002
#define int long long
using namespace std;
ifstream fin ("cmap.in");
ofstream fout("cmap.out");
int nr;

struct el
{
    int x,y;
}v[dim],w[dim],mid;

inline bool cmp (const el &a1,const el &a2)
{
    if (a1.x==a2.x)
        return a1.y<a2.y;
    return a1.x<a2.x;
}


long long dist (int i,int j)
{
    long long sol=(v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y);
    return sol;
}

long long dist2 (int i,int j)
{
    long long sol=(w[i].x-w[j].x)*(w[i].x-w[j].x)+(w[i].y-w[j].y)*(w[i].y-w[j].y);
    return sol;
}

void inter (int st,int dr)
{
    nr=0;
    int mij=(st+dr)/2;
    int i=st,j=mij+1;
    while (i<=mij && j<=dr)
    {
        while (i<=mij  && v[i].y<=v[j].y)
            w[++nr]=v[i++];
        if (i<=mij)
        while (j<=dr && v[j].y<=v[i].y)
            w[++nr]=v[j++];
    }
    for (;i<=mij;i++)
        w[++nr]=v[i];
    for (;j<=dr;j++)
        w[++nr]=v[j];
    nr=1;
    for (i=st;i<=dr;i++)
        v[i]=w[nr++];
}

long long rez (int st,int dr)
{
    if (st==dr)
        return 1e17;
    int i,j,mij=(st+dr)/2;
    mid=v[mij];
    long long s1=rez(st,mij),s2=rez(mij+1,dr);
    long long s=min(s1,s2);
    inter (st,dr);
    nr=0;
    for (i=st;i<=dr;i++)
        if ((v[i].x-mid.x)*(v[i].x-mid.x)<=s)
        w[++nr]=v[i];
    for (i=1;i<=nr;i++)
        for (j=i-1;j>=i-8&&j>=1;--j)
        if (dist2(i,j)<s)
        s=dist2(i,j);
    return s;
}

int32_t main ()
{
    int n,i;
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sort (v+1,v+n+1,cmp);
    long long sol=rez(1,n);
    long double Q=sqrtl(sol);
    fout<<fixed<<setprecision(6)<<Q;
}