Cod sursa(job #1865403)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 1 februarie 2017 18:49:57
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <climits>
#define inf 0x3f3f3f3f

using namespace std;

struct Coord {
    int x, y;
    inline double dist(const Coord& a) {
        return sqrt((double)((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)));
    }
} v[100001];
int n;

inline bool cmp(const Coord& a, const Coord& b) {
    return a.x < b.x;
}

int cautlb(int st, int dr, int val)
{
    int mid;
    while(st < dr)
    {
        mid = (st + dr) / 2;
        if(v[mid].x <= val)
            dr = mid;
        else st = mid + 1;
    }
    mid = (st + dr) / 2;
    if(v[mid].x < val)
        mid++;
    return mid;
}

int cautub(int st, int dr, int val)
{
    int mid;
    while(st < dr)
    {
        mid = (st + dr) / 2;
        if(v[mid].x < val)
            dr = mid;
        else st = mid + 1;
    }
    mid = (st + dr) / 2;
    if(v[mid].x > val)
        mid--;
    return mid;
}

double dmin(int st, int dr)
{
    if(dr - st <= 2)
    {
        double rez = 99999999;
        for(int i = st; i < dr; i++)
            for(int j = i + 1; j <= dr; j++)
                rez = min(rez, v[i].dist(v[j]));
        return rez;
    }
    double m1 = dmin(st, (st + dr) / 2);
    double m2 = dmin((st + dr) / 2 + 1, dr);
    int delta = min(ceil(m1), ceil(m2));
    int st1 = cautlb(st, (st + dr) / 2, v[(st + dr) / 2].x - delta);
    int dr1 = cautub((st + dr) / 2 + 1, dr, v[(st + dr) / 2 + 1].x + delta);
    double m3 = dmin(st1, dr1);
    return min(m1, min(m2, m3));
}

int main()
{
    int i;
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    scanf("%d", &n);
    for(i = 0; i < n; i++) {
        scanf("%d%d", &v[i].x, &v[i].y);
    }
    sort(v, v + n, cmp);
    double rez = dmin(0, n - 1);
    printf("%f", rez);
    return 0;
}