Cod sursa(job #2471982)

Utilizator Vlad.Vlad Cristian Vlad. Data 11 octombrie 2019 20:51:28
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct point{
    int x, y;
};
int n;
point v[10005];
void citire() {
    fin >> n;
    for (int i = 0; i < n; ++i) {
        fin >> v[i].x >> v[i].y;
    }
}
bool comp(point p1, point p2) {
    return p1.x < p2.x;
}
double dBetween2(point p1, point p2) {
    int x = p1.x - p2.x;
    int y = p1.y - p2.y;
    return sqrt(x * x + y * y);
}
void intercl(int st, int mij, int dr) {
    int i = st, j = mij;
    vector<point> aux;
    while (i < mij && j <= dr) {
        if (v[i].y < v[j].y) {
            aux.push_back(v[i]);
            ++i;
        }
        else {
            aux.push_back(v[j]);
            ++j;
        }
    }
    while (i < mij) {
        aux.push_back(v[i++]);
    }
    while (j <= dr) {
        aux.push_back(v[j++]);
    }
    for (unsigned l = 0; l < aux.size(); ++l) {
        v[l + st] = aux[l];
    }
}
double det(int st, int dr) {
    double ans = 99999999999;
    if (st >= dr)
        return ans;
    if (dr - st == 1) {
        if (v[st].y > v[dr].y) {
            swap(v[st], v[dr]);
        }
        return dBetween2(v[st], v[dr]);
    }
    int mij = (st + dr) / 2;
    ans = min(det(st, mij), det(mij + 1, dr));
    intercl(st, mij, dr);
    for (int i = st; i <= dr; ++i) {
        for (int j = i + 1; j <= dr && j - i >= 6; ++j) {
            ans = min(dBetween2(v[i], v[j]), ans);
        }
    };
    return ans;
}
int main()
{
    citire();
    sort(v, v + n, comp);
    fout << fixed << setprecision(6) << det(0, n - 1) << "\n";
    return 0;
}