Cod sursa(job #1364079)

Utilizator vtt271Vasile Toncu vtt271 Data 27 februarie 2015 14:04:05
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
//cele mai apropiate puncte in plan
using namespace std;

double inf = 10000000000000000;

inline double sqr(double x)
{
    return x*x;
}

struct punct{
    double x, y;
};

int n;

double dist(punct q, punct w)
{
    return sqrt( sqr(q.x-w.x) + sqr(q.y-w.y) );
}

double min_dist(punct *A, int left, int right) {
    if(left == right) return inf;
    if(left+1 == right) return dist(A[left], A[right]);
    int mid = (left+right)/2;
    double dist1 = min(min_dist(A, left, mid), min_dist(A, mid+1, right));

    vector <punct> Y;
    for(int i = left; i <= right; i++) {
        if( dist(A[i], A[mid]) < dist1 ) {
            Y.push_back(A[i]);
        }
    }

    for(int i = 0; i < Y.size(); i++ ){
        for(int j = i+1; j < Y.size() && i+7 > j; j++) {
            if( dist(Y[i], Y[j]) < dist1 ) {
                dist1 = dist(Y[i], Y[j]);
            }
        }
    }

    return dist1;
}

bool cmp(punct q, punct w)
{
    return q.x <= w.x;
}

int main()
{
    ifstream inFile("cmap.in");
    ofstream outFile("cmap.out");


    inFile >> n;
    punct A[100004];
    double x, y;
    punct p;

    for(int i = 1; i <= n; i++) {
        inFile >> x >> y;
        p.x = x;
        p.y = y;
        A[i] = p;
    }
    sort(A+1, A+1+n, cmp);

    outFile << fixed << setprecision(6) << min_dist(A, 1, n);

}