Cod sursa(job #2138032)

Utilizator mariakKapros Maria mariak Data 21 februarie 2018 11:34:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>
#define point pair< double, double >
#define x first
#define y second
FILE *fin  = freopen("cmap.in", "r", stdin);
FILE *fout = freopen("cmap.out", "w", stdout);

using namespace std;
/*---------Data--------*/
const int MAX = 1e5 + 2;
const int INF = 2e9 + 2;
int n;
point p[MAX];
struct comp{
    bool operator () (const int &a, const int &b) const{
        return p[a].y < p[b].y;
    }
};

void Read(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i)
        scanf("%lf%lf", &p[i].x, &p[i].y);
}

double Dist(point p1, point p2){
    return sqrt(1LL * (p1.y - p2.y) * (p1.y - p2.y) +
                1LL * (p1.x - p2.x) * (p1.x - p2.x));
}

double StripClosest(int strip[], int len, double d){
    double ans = d;
    sort(strip, strip + len, comp());

    for(int i = 0; i < len; ++ i){
        point p1 = p[strip[i]];
        for(int j = i + 1; j < len; ++ j){
            point p2 = p[strip[j]];
            if((p2.y - p1.y) >= d) break;
            ans = min(ans, Dist(p1, p2));
        }
    }
    return ans;
}

double BruteForce(int left, int right){
    double ans = INF;
    for(int i = left; i < right; ++ i)
        for(int j = left + 1; j <= right; ++ j)
            ans = min(ans, Dist(p[i], p[j]));
    return ans;
}

double Divide(int left, int right){
    if(right - left < 2)
        return BruteForce(left, right);

    int mid = (left + right) >> 1;
    double d = Divide(left, mid);
    d = min(d, Divide(mid + 1, right));

    int strip[n];
    int j = 0;

    for(int i = left; i <= right; ++ i)
        if(abs(p[mid].x - p[i].x) < d)
            strip[j ++] = i;

    return min(d, StripClosest(strip, j, d));
}

int main(){
    Read();
    sort(p, p + n);
    printf("%.10f\n", Divide(0, n - 1));
    return 0;
}