Cod sursa(job #1687436)

Utilizator martonsSoos Marton martons Data 12 aprilie 2016 21:06:39
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <climits>

using namespace std;

struct punct{
    int x, y;
};

punct v[100000];

bool sort_by_x(punct a, punct b){
    if(a.x>b.x)return true;
    else return false;
}

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

double solve_s(punct* s, punct* m, punct* e, double min_dst){
    while(m->x - s->x > min_dst)s++;
    while(e->x - m->x > min_dst)e--;

    for(;s<e;s++){
        for(int i=1;i<7&&i+s<e;i++){
            double t=dist(*s, *(s+i));
            if(t<min_dst){
                min_dst=t;
            }
        }
    }

    return min_dst;
}

double solve(punct* s, punct* e){
    double minim=INT_MAX;
    if(e-s<=3){
        for(punct* it0=s;it0<e;it0++){
            for(punct* it1=it0+1;it1<e;it1++){
                double t=dist(*it0, *it1);
                if(t<minim){
                    minim=t;
                }
            }
        }
        return minim;
    }

    return solve_s(s, s+((e-s)/2), e, min(solve(s, s+((e-s)/2)),solve(s+((e-s)/2), e)));
}

int main()
{
    FILE* f=fopen("cmap.in", "r");

    int n;
    fscanf(f, "%d", &n);

    for(int i=0;i<n;i++)
        fscanf(f, "%d %d", &v[i].x, &v[i].y);

    sort(v, v+n, sort_by_x);
    fclose(f);

    f=fopen("cmap.out", "w");
    fprintf(f, "%f", solve(v, v+n));

    return 0;
}