Cod sursa(job #3342655)

Utilizator BidonTurtitBezdedan Eric BidonTurtit Data 25 februarie 2026 10:24:25
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#define NMax 100005
#define inf 2e9
using namespace std;

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

struct punct
{
    int x,y;
} p[NMax],y[NMax];

int n;

bool cresc(punct a,punct b)
{
    if(a.x<b.x)
        return 1;
    else if(a.x==b.x)
    {
        if(a.y<b.y)
            return 1;
    }
    return 0;
}

double rez(int st, int dr)
{
    double mn=inf;
    int mij=(st+dr)/2;
    if(dr-st+1<=3)
    {
        for(int i=st; i<dr; i++)
        {
            for(int j=i+1; j<=dr; j++)
            {
                int dx=p[i].x-p[j].x;
                int dy=p[i].y-p[j].y;
                mn=min(mn,sqrt(dx*dx+dy*dy));
            }
        }
        return mn;
    }
    else
    {
        mn=min(rez(st,mij),rez(mij+1,dr));
    }
    int cnt=0,i=st,j=mij+1;
    while(i<=mij && j<=dr)
    {
        if(p[i].y<p[j].y)
        {
            y[++cnt]=p[i];
            i++;
        }
        else
        {
            y[++cnt]=p[j];
            j++;
        }

    }
    while(i<=mij)
    {
        y[++cnt]=p[i];
        i++;
    }
    while(j<=dr)
    {
        y[++cnt]=p[j];
        j++;
    }
    for(int i=1; i<=cnt; i++)
    {
        p[st+i-1]=y[i];
    }
    for(int i=st; i<=dr; i++)
    {
        for(int j=i+1; j<=i+7 && j<=dr; j++)
        {
            if(abs(p[i].x-p[mij].x)<=mn)
            {
                int dx=p[i].x-p[j].x;
                int dy=p[i].y-p[j].y;
                mn=min(mn,sqrt(dx*dx+dy*dy));
            }

        }
    }
    return mn;



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