Cod sursa(job #2074067)

Utilizator Dupree7FMI Ciobanu Andrei Dupree7 Data 24 noiembrie 2017 01:57:45
Problema Cele mai apropiate puncte din plan Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;

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

struct point{
    int x, y;
};

bool cmp(point a, point b){
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

long long d(point a, point b){
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}

int n;

long long minDist(int l, int r, vector<point>& points){
    if(r - l == 1)
        return d(points[l], points[r]);
    else if(r - l == 2){
        return min(d(points[l], points[l + 1]), min(d(points[l], points[l + 2]), d(points[l + 1], points[l + 2])));
    }else{
        int mid = (l + r) / 2;
        long long midL = minDist(l, mid, points);
        long long midR = minDist(mid, r, points);
        long long minD = min(midL, midR);

        vector<point> aux;
        for(int i = l; i < mid; i++)
            if(d(points[i], points[mid]) < minD)
                aux.push_back(points[i]);
        for(int i = mid + 1; i <= r; i++)
            if(d(points[i], points[mid]) < minD)
                aux.push_back(points[i]);

        for(int i = 0; i < (int)aux.size(); i++)
            for(int j = 0; j < (int)aux.size(); j++)
                if(j != i && d(aux[i], aux[j]) < minD)
                    minD = d(aux[i],aux[j]);

        return minD;
    }
}

int main()
{
    vector<point> points;
    f >> n;
    for(int i = 0; i < n; i++){
        point t;
        f >> t.x >> t.y;
        points.push_back(t);
    }
    sort(points.begin(), points.end(), cmp);

    g << fixed << setprecision(6) << sqrt(minDist(0, n - 1, points));
    return 0;
}