Cod sursa(job #3348333)

Utilizator Lex._.Lex Guiman Lex._. Data 20 martie 2026 20:27:05
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.17 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], aux[NMAX+1];

void interclasare(int st, int mij, int dr)
{
    int i=st, j=mij+1, k=0;
    while(i<=mij && j<=dr)
    {
        if(puncte[i].y<puncte[j].y) aux[k++]=puncte[i++];
        else aux[k++]=puncte[j++];
    }
    while(i<=mij) aux[k++]=puncte[i++];
    while(j<=dr) aux[k++]=puncte[j++];
    for(int l=0; l<k; l++) puncte[st+l]=aux[l];
}

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
{
    int mij=st+(dr-st)/2;
    if(dr-st<=2)
    {
        long double minim=dist(puncte[st], puncte[dr]);
        if(dr-st==2)
        {
            minim=min(minim, dist(puncte[st], puncte[mij]));
            minim=min(minim, dist(puncte[mij], puncte[dr]));
        }
        interclasare(st, mij, dr);
        return minim;
    }
    int d=puncte[mij].x; ///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);
    interclasare(st, mij, 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].x)<dist_min)
            candidati.push_back(puncte[i]);
    }
    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;
}