Cod sursa(job #1308237)

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

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

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

ll 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]);
    }

    ll 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);
    freopen("cmap.out","w",stdout);
    printf("%lf", sqrt((double)minimalDistance(1, N)));

return 0;
}