Cod sursa(job #1750818)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 31 august 2016 03:35:10
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i64; ///Deci de aici am eu obiceiul...

const i64  INF = 1LL << 62;
const int NMAX = 100005;

struct PII {
    int x, y;

    inline PII() { }
    inline PII(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

PII pts[NMAX], aux[NMAX];

bool cmp_x(const PII &a, const PII &b) {
    return (a.x==b.x) ? (a.y < b.y) : (a.x < b.x);
}

bool cmp_y(const PII &a, const PII &b) {
    return (a.y==b.y) ? (a.x < b.x) : (a.y < b.y);
}

inline i64 dist(const PII &a, const PII &b) {
    return i64(a.x - b.x) * (a.x - b.x) + i64(a.y - b.y) * (a.y - b.y);
}

i64 ant(int st, int dr) {
    if(dr-st<=0) return INF;
    if(dr-st==1) return dist(pts[st], pts[dr]);

    int med = (st + dr) / 2,
        aln = 0,
         mx = pts[med].x;
    i64 ans = min(ant(st, med), ant(med+1, dr));

    merge(pts+st, pts+med+1, pts+med+1, pts+dr+1, aux, cmp_y);
    for(int i=0; i<=dr-st; ++i)
        pts[i+st] = aux[i];

    for(int i=st; i<=dr; ++i) {
    if(i64(mx - pts[i].x) <= ans) {
        aux[aln++] = pts[i];
    }}


    for(int i=0; i<aln; ++i)
    for(int j=i+1; j<aln && j-i<=8; ++j)
        ans = min(ans, dist(pts[i], pts[j]));

    return ans;
}

int main(void) {
    freopen("cmap.in",  "r", stdin);
    freopen("cmap.out", "w", stdout);
    int n, x, y;

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

    sort(pts, pts+n, cmp_x);

    printf("%.6f\n",sqrt(1.*ant(0, n-1)));

    fclose(stdin);
    fclose(stdout);
    return 0;
}