Cod sursa(job #3345917)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 11 martie 2026 19:17:28
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.03 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>

using namespace std;

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

const long long INF = (1LL << 63) - 1;

struct Point
{
    int x, y;
    Point(int xx = 0, int yy = 0): x(xx), y(yy) {}
    Point& operator = (const Point &p)
    {
        x = p.x;
        y = p.y;
        return *this;
    }
    inline bool operator < (const Point &p) const
    {
        return (x < p.x || (x == p.x && y < p.y));
    }
    friend istream& operator >> (istream& in, Point &p)
    {
        in >> p.x >> p.y;
        return in;
    }
};

vector<Point> X, /// X - punctele ordonate crescator dupa x
              Y; /// Y - punctele ordonate crescator dupa y
int N;

inline long long Abs(long long x) { return x < 0 ? -x : x; }

inline long long Min(long long x, long long y) { return x < y ? x : y; }

inline void MinSelf(long long &x, long long y) { x = (x < y ? x : y); }

long long Dist(Point &p1, Point &p2)
{
    long long dx = p1.x - p2.x,
        dy = p1.y - p2.y;
    return (long long)dx * dx + (long long)dy * dy;
}

/// Interclaseaza Y[st..mid] si Y[mid + 1..dr], iar
/// rezultatul va fi pastrat in Y[st..dr]
void Merge(vector<Point> &Y, int st, int mid, int dr)
{
    vector<Point> V;
    int i = st, j = mid + 1;
    while(i <= mid && j <= dr)
        if(Y[i] < Y[j])
            V.push_back(Y[i++]);
        else
            V.push_back(Y[j++]);
    while(i <= mid)
        V.push_back(Y[i++]);
    while(j <= dr)
        V.push_back(Y[j++]);
    for(i = st; i <= dr; i++)
        Y[i] = V[i - st];
}

long long GetMinDist(int st, int dr,
                     vector<Point> &X, vector<Point> &Y)
{
    if(st > dr)
        return INF;
    if(dr - st <= 2) /// Multimea contine maxim 3 elemente
    {
        long long dist = INF;
        for(int i = st; i < dr; i++)
            for(int j = i + 1; j <= dr; j++)
                MinSelf(dist, Dist(X[i], X[j]));
        sort(Y.begin() + st, Y.begin() + dr);
        return dist;
    }
    int mid = st + ((dr - st) >> 1);
    long long dist = Min(GetMinDist(st, mid, X, Y),
                         GetMinDist(mid + 1, dr, X, Y));
    Merge(Y, st, mid, dr);
    vector<Point> V;
    for(int i = st; i <= dr; i++)
        if(Abs(Y[i].y - X[mid].x) <= dist)
            V.push_back(Y[i]);
    for(int i = 0; i < (int)V.size() - 1; i++)
        for(int j = i + 1; j < (int)V.size() && j - i < 8; j++)
            MinSelf(dist, Dist(V[i], V[j]));
    return dist;
}

void Read()
{
    f >> N;
    X.resize(N); Y.resize(N);
    for(int i = 0; i < N; i++)
        f >> X[i];
}

void SortPoints()
{
    sort(X.begin(), X.end());
    for(int i = 0; i < N; i++)
        Y[i] = Point(X[i].y, X[i].x);
}

void FindDist()
{
    double minDist = sqrt(GetMinDist(0, N - 1, X, Y));
    g << fixed << setprecision(6) << minDist << '\n';
}

int main()
{
    Read();
    SortPoints();
    FindDist();
    f.close();
    g.close();
    return 0;
}