Cod sursa(job #1364010)

Utilizator vtt271Vasile Toncu vtt271 Data 27 februarie 2015 13:38:00
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
//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;
};

double min_dist(punct *A, int left, int right) {
    if(left == right) return inf;
    if(left+1 == right) return sqr(A[left].x - A[right].x) + sqr(A[left].y - A[right].y);
    int mid = (left+right)/2;
    double d = min(min_dist(A, left, mid), min_dist(A, mid, right));
    return d;
}

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

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

    int n;
    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);
    for(int i = 1; i <= n; i++) {
        outFile << A[i].x << " " << A[i].y << "\n";
    }

    outFile << sqrt(min_dist(A, 1, n));

}