Cod sursa(job #1310711)

Utilizator thesvcoolmanLucian Bicsi thesvcoolman Data 7 ianuarie 2015 08:48:30
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iomanip>
#define INF 1000000002

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

struct Point {
    double x, y;
    Point(int t, int u) {
        x = t; y = u;
    }
};

double dist(Point a, Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

bool cmp(Point a, Point b) {
    return a.y<b.y;
}
int n;
vector<Point> A;

double dmin(int ls, int ld) {
    if(ls == ld) return INF;
    if(ld == ls+1) return dist(A[ls], A[ld]);
    int mid = (ls+ld)/2;
    double MIN = min(dmin(ls, mid), dmin(mid+1, ld));
    for(int i1 = mid; A[i1].y>A[mid].y-MIN && i1; i1--) {
        for(int i2 = mid+1; A[i2].y<A[mid].y+MIN && i2<n; i2++) {
            MIN = min(MIN, dist(A[i1], A[i2]));
        }
    }
    return MIN;
}

int main()
{
    int a,b;
    fin>>n;
    for(int i=1; i<=n; i++) {
        fin>>a>>b;
        A.push_back(Point(a,b));
    }
    sort(A.begin(), A.end(), cmp);

    fout<<setprecision(20)<<dmin(0, n-1);
    return 0;
}