Cod sursa(job #3331304)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 26 decembrie 2025 15:04:11
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 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
    {
        return (x == other.x ? y < other.y : 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 closest_points(int st, int dr)
{
    double dist_min = DBL_MAX;
    if(dr - st + 1 <= 3)
    {
        for(int i = st; i <= dr; i++)
            for(int j = i + 1; j <= dr; j++)
                dist_min = min(dist_min, dist(points[i], points[j]));
        for(int i = st; i <= dr; i++)
            for(int j = i + 1; j <= dr; j++)
                if(points[i].y > points[j].y)
                    swap(points[i], points[j]);
        return dist_min;
    }
    int mid = (st + dr) / 2;
    dist_min = min({dist_min, closest_points(st, mid), closest_points(mid + 1, dr)});
    inplace_merge(points + st, points + mid + 1, points + dr + 1, [&](Point A, Point B) { return (A.y < B.y); });
    for(int i = st; i <= dr; i++)
        for(int j = 1; j <= 7 && i + j <= dr; j++)
            dist_min = min(dist_min, dist(points[i], points[i + j]));
    return dist_min;
}

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) << closest_points(1, n);

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