Cod sursa(job #2058294)

Utilizator gorneanu.andreiFMI Gorneanu Andrei gorneanu.andrei Data 5 noiembrie 2017 14:05:34
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#define inf 9999999
using namespace std;

struct punct{
    int x, y;
}a[100010], b[100010];

int n;

bool cmpX(punct c,punct d){

    return (c.x < d.x);
}

bool cmpY(punct c,punct d){

    return (c.y < d.y);
}
double dist(punct c,punct d){

    return sqrt((c.x - d.x) * (c.x - d.x) + (c.y - d.y) * (c.y - d.y));
}

double solve(int st,int dr){

    if(dr - st <= 0)
        return inf;
    else if(dr - st == 1){
        return dist(a[st],a[dr]);
    }

    int mid = (st + dr) / 2;
    double d = min(solve(st,mid),solve(mid + 1,dr));

    vector<punct> c;
    int len = 0;
    for(int i = 0;i < n; ++i)
        if(abs(b[i].x - a[mid].x) < d){
            c.push_back(b[i]);
            ++len;
        }

    int j;
    for(int i = 0;i < len; ++i)
        for(j = i + 1;j <= i + 8 && j < len; ++j)
            d = min(d,dist(c[i],c[j]));

    return d;
}

int main(){

    fstream f("cmap.in",ios::in);
    fstream g("cmap.out",ios::out);

    f >> n;

    for(int i = 0;i < n; ++i){
        f >> a[i].x >> a[i].y;
        b[i] = a[i];
    }

    sort(a,a + n,cmpX);
    sort(b,b + n,cmpY);

    double answ = solve(0,n - 1);
    g << fixed << setprecision(6) << answ;

    f.close();
    g.close();
    return 0;
}