Cod sursa(job #2074073)

Utilizator Dupree7FMI Ciobanu Andrei Dupree7 Data 24 noiembrie 2017 02:51:08
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <limits.h>

using namespace std;

#define x first
#define y second
#define nMax 100000

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

int n;
pair<int, int> points[nMax], pointsY[nMax], aux[nMax];

long long d(pair<int, int> a, pair<int, int> b){
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}

long long minDist(int l, int r){
    if(r == l)
        return INT_MAX;
    else if(r - l == 1){
        if(pointsY[r] < pointsY[l])
            swap(pointsY[l], pointsY[r]);
        return d(pointsY[l], pointsY[r]);
    }
    int mid = (l + r) >> 1;
    long long minD = min( minDist(l, mid), minDist(mid + 1, r));
    merge(pointsY + l, pointsY + mid + 1, pointsY + mid + 1, pointsY + r + 1, aux);
    copy(aux, aux + (r - l + 1), pointsY + l);

    int k = 0;
    for(int i = l; i <= r; i++)
        if(abs(points[mid].x - pointsY[i].y) <= minD && i != mid)
            aux[k++] = pointsY[i];

    for(int i = 0; i < k; i++)
        for(int j = i + 1; j < k && j <= i + 8; j++)
            minD = min(minD, d(aux[i], aux[j]));

    return minD;
}

int main()
{
    f >> n;
    for(int i = 0; i < n; i++)
        f >> points[i].x >> points[i].y;

    sort(points, points + n);
    for(int i = 0; i < n; i++)
        pointsY[i] = make_pair(points[i].y, points[i].x);

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