Cod sursa(job #3348319)

Utilizator Lex._.Lex Guiman Lex._. Data 20 martie 2026 19:04:51
Problema Cele mai apropiate puncte din plan Scor 55
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>
#define NMAX 100000
#define x first
#define y second
using namespace std;

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

pair<int, int> puncte[NMAX+1];

long double dist(pair<int, int> a, pair<int, int> b) ///distanta intre 2 puncte
{
    return sqrt(((long double)a.x-b.x)*(a.x-b.x) + ((long double)a.y-b.y)*(a.y-b.y));
}

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}

long double solve(int st, int dr) ///divide et impera
{
    if(dr-st<=2)
    {
        long double minim=dist(puncte[st], puncte[dr]);
        if(dr-st==2)
        {
            minim=min(minim, dist(puncte[st], puncte[st+1]));
            minim=min(minim, dist(puncte[st+1], puncte[dr]));
        }
        return minim;
    }
    int mij=st+(dr-st)/2;
    int d=puncte[mij].y; ///coordonata dreptei care imparte punctele in doua multimi
    long double dist_st=solve(st, mij);
    long double dist_dr=solve(mij+1, dr);
    long double dist_min=min(dist_st, dist_dr);
    vector<pair<int, int>> candidati; ///punctele situate la o distanta mai mica ca dist_min fata de dreapta d
    for(int i=st; i<=dr; i++)
    {
        if(abs(d-puncte[i].y)<dist_min)
            candidati.push_back(puncte[i]);
    }
    sort(candidati.begin(), candidati.end(), cmp);
    for(int i=0; i<candidati.size(); i++)
    {
        for(int j=i+1; j<candidati.size() && j<i+8; j++)
        {
            dist_min=min(dist_min, dist(candidati[i], candidati[j]));
        }
    }
    candidati.clear();
    return dist_min;
}

int main()
{
    int n;
    in >> n;
    for(int i=1; i<=n; i++)
    {
        in >> puncte[i].x >> puncte[i].y;
    }
    sort(puncte+1, puncte+n+1);
    out << fixed << setprecision(6) << solve(1, n);

    return 0;
}