Cod sursa(job #3154233)

Utilizator divadddDavid Curca divaddd Data 3 octombrie 2023 20:31:45
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>
#define mp make_pair
// #define int long long
using namespace std;
using db = double long;
const int NMAX = 1e5+2;
int n;

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

struct Point {
    int x;
    int y;

    bool operator < (const Point &aux) const {
        return mp(x, y) < mp(aux.x, aux.y);
    }

};

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

db mindist(vector<Point> points, vector<Point> ysort){
    int n = points.size();
    if(n == 1){
        return 1e18; // nu exista pereche
    }
    vector<Point> left = vector<Point>(points.begin(), points.begin()+n/2);
    vector<Point> right = vector<Point>(points.begin()+n/2, points.end());

    Point midpoint = left.back();
    vector<Point> left_ysort, right_ysort;
    for(auto it: ysort){
        if(it < midpoint){
            left_ysort.push_back(it);
        }else{
            right_ysort.push_back(it);
        }
    }
    db ldist = mindist(left, left_ysort);
    db rdist = mindist(right, right_ysort);
    db ans = min(ldist, rdist);

    vector<Point> cadran;
    for(auto it: ysort){
        db distx = (it.x - midpoint.x) * (it.x - midpoint.x);
        if(distx < ans){
            cadran.push_back(it);
        }
    }

    n = cadran.size();
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            ans = min(ans, dist(cadran[i], cadran[j]));
        }
    }
    return ans;
}

signed main(){
    fin >> n;
    vector<Point> points(n), ysort(n);
    for(auto &it: points){
        fin >> it.x >> it.y;
    }
    ysort = points;
    sort(points.begin(), points.end());
    sort(ysort.begin(), ysort.end(), [](const Point &a, const Point &b){
        return a.y < b.y;
    });
    fout << fixed << setprecision(10) << sqrtl(mindist(points, ysort));
    return 0;
}