Cod sursa(job #1308227)

Utilizator morlockRadu Tatomir morlock Data 3 ianuarie 2015 19:36:29
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <utility>
#define nmax 100005
#define ll long long
using namespace std;

ifstream in("cmap.in");
ofstream out("cmap.out");
pair<ll,ll> point[nmax];
pair<ll,ll> V[nmax];
int N;

double dist(pair<ll, ll> p1, pair<ll, ll> p2) {
    return sqrt((p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second));
}

double minimalDistance(int left, int right) {
    int mid = (left + right) >> 1;
    if (left >= right)
        return 1LL << 62;
    if (left + 1 == right) {
        if ( point[left].second > point[right].second )
            swap(point[left], point[right]);
        return dist(point[left], point[right]);
    }

    double minDist = min(minimalDistance(left, mid), minimalDistance(mid + 1, right));

    merge(point + left, point + mid + 1, point + mid + 1, point + right + 1, V);

    int nr = 0;
    for (int i = left; i <= right; i++) {
        if ( abs(point[i].first - point[mid].first) <= minDist)
            V[++nr] = point[i];
    }

     for (int i=1; i<right; i++) {
        for (int j=i+1; j<=min(i+5, nr); j++)
            minDist = min(minDist, dist(V[j], V[i]));
    }

    return minDist;
}

int main() {
    in >> N;
    for (int i=1; i<=N; ++i) {
        in >> point[i].first >> point[i].second;
    }

    sort(point + 1, point + N + 1);
    //for (int i=1; i<=N; ++i)
        //cout << point[i].first << " " << point[i].second << '\n';

    out << minimalDistance(1, N);

return 0;
}