Cod sursa(job #3345257)

Utilizator Carnu_EmilianCarnu Emilian Carnu_Emilian Data 8 martie 2026 19:09:10
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long double ld;

const int N = 1e5 + 5;
int n;
pair<int, int> v[N];

ld distanta(pair<int, int> p1, pair<int, int> p2)
{
    int dx, dy;
    dx = p1.first - p2.first;
    dy = p1.second - p2.second;
    return hypot(dx, dy);
}

bool comp(pair<int, int> &p1, pair<int, int> &p2)
{
    if (p1.second == p2.second)
        return p1.first < p2.first;
    return p1.second < p2.second;
}

ld divide(int st, int dr)
{
    if (st == dr)
        return 1e18;
    if (st == dr - 1)
        return distanta(v[st], v[dr]);
    int m = (st + dr) / 2;
    int x = v[m].first;
    ld r1, r2, dmin;
    r1 = divide(st, m);
    r2 = divide(m + 1, dr);
    dmin = min(r1, r2);
    vector<pair<int, int>> a;
    for (int i = st; i <= dr; i++)
        if (abs(v[i].first - x) <= dmin)
            a.push_back(v[i]);
    sort(a.begin(), a.end(), comp);
    for (int i = 0; i < a.size(); i++)
        for (int j = i + 1; j < a.size() && abs(a[i].second - a[j].second) < dmin; j++)
        {
            dmin = min(dmin, distanta(a[i], a[j]));
        }
    return dmin;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i].first >> v[i].second;
    sort(v + 1, v + n + 1);
    ld rasp = divide(1, n);
    fout << fixed << rasp;
    return 0;
}