Cod sursa(job #3330740)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 21 decembrie 2025 17:23:33
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int NMAX = 1e5 + 1;
struct Point
{
    double x, y;
    bool operator < (const Point &other) const
    {
        if(x == other.x)
            return (y < other.y);
        return (x < other.x);
    }
} points[NMAX];

double dist(Point A, Point B)
{
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

double solve(int st, int dr)
{
    double ans = 1e18;
    if(dr - st + 1 <= 3)
    {
        for(int i = st; i <= dr; i++)
            for(int j = i + 1; j <= dr; j++)
                ans = min(ans, dist(points[i], points[j]));
    }
    else
    {
        int mid = (st + dr) / 2;
        vector<Point> sorted;
        ans = min({ans, solve(st, mid), solve(mid + 1, dr)});
        for(int i = st; i <= dr; i++)
        {
            double dif = abs(points[mid].x - points[i].x);
            if(dif < ans)
                sorted.push_back(points[i]);
        }
        sort(sorted.begin(), sorted.end(), [&] (Point A, Point B) { return (A.y < B.y); });
        for(int i = 0; i < sorted.size(); i++)
            for(int j = i + 1; j < sorted.size() && j - i <= 8; j++)
                ans = min(ans, dist(sorted[i], sorted[j]));
    }
    return ans;
}

int main()
{
    int n;
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> points[i].x >> points[i].y;
    sort(points + 1, points + n + 1);
    fout << fixed << setprecision(6) << solve(1, n);

    fin.close();
    fout.close();
    return 0;
}