Cod sursa(job #3342691)

Utilizator BidonTurtitBezdedan Eric BidonTurtit Data 25 februarie 2026 11:28:52
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#define NMax 100005
#define inf 2000000000000000000LL
using namespace std;

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

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

int n;

bool crescy(punct a,punct b)
{
    if(a.y<b.y)
        return 1;
    else if(a.y==b.y)
    {
        if(a.x<b.x)
            return 1;
    }
    return 0;
}
bool crescx(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;
}

long long int rez(int st, int dr)
{
    int mijx;
    long long int 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++)
            {
                long long int dx=p[i].x-p[j].x;
                long long int dy=p[i].y-p[j].y;
                mn=min(mn,dx*dx+dy*dy);
            }
        }
        sort(p+st+1,p+dr+1,crescy);
        return mn;
    }
    else
    {
        mijx=p[mij].x;
        mn=min(rez(st,mij),rez(mij+1,dr));
    }
    sort(p+st+1,p+dr+1,crescy);
    for(int i=st; i<=dr; i++)
    {
        for(int j=i+1; j<=i+7 && j<=dr; j++)
        {
            if(1LL*(p[i].x-mijx)*(p[i].x-mijx)<=mn)
            {
                long long int dx=p[i].x-p[j].x;
                long long int dy=p[i].y-p[j].y;
                mn=min(mn,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,crescx);
    fout<<fixed<< setprecision(6)<<sqrt(rez(1,n));
    return 0;
}