Cod sursa(job #3271243)

Utilizator BucsMateMate Bucs BucsMate Data 25 ianuarie 2025 15:01:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <climits>
#include <iomanip>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const long long INF = LLONG_MAX/4;

struct Point
{
    long long x = 0;
    long long y = 0;
};

long long dist(Point a, Point b)
{
    return ((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

bool compx(Point a, Point b)
{
    return (a.x < b.x);
}

bool compy(Point a, Point b)
{
    return (a.y < b.y);
}

long long div_et_imp(vector<Point> &px, vector<Point> &py, vector<Point> &pseged, int left, int right)
{
    if(right - left < 2){
        return INF;
    }
    else if(right - left == 2){
        if(py[left].y > py[left+1].y){
            Point temp = py[left];
            py[left] = py[left+1];
            py[left+1] = temp;
        }
        return dist(px[left], px[left+1]);
    }

    int mid = (left + right)/2;
    long long best = min(div_et_imp(px, py, pseged, left, mid), div_et_imp(px, py, pseged, mid, right));

    merge(py.begin() + left, py.begin() + mid, py.begin() + mid, py.begin() + right, pseged.begin(), compy);
    copy(pseged.begin(), pseged.begin() + (right - left), py.begin() + left);

    int nr_points = 0;
    for(int i = left; i < right; i++){
        if(abs(px[mid].x - py[i].x) <= best){
            pseged[nr_points] = py[i];
            nr_points++;
        }
    }

    for(int i = 0; i < nr_points-1; i++){
        for(int j = i+1; j < nr_points && j-i < 8; j++){
            best = min(best, dist(pseged[i], pseged[j]));
        }
    }
    return best;
}

int main()
{
    int n;
    fin >> n;
    vector<Point> px(n), py(n), pseged(n);
    for(int i = 0; i < n; i++){
        fin >> px[i].x >> px[i].y;
    }

    sort(px.begin(), px.end(), compx);
    for(int i = 0; i < n; i++){
        py[i] = px[i];
    }
    fout << fixed << setprecision(6) << sqrt(div_et_imp(px, py, pseged, 0, n));

    return 0;
}