Cod sursa(job #1534022)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 23 noiembrie 2015 10:39:50
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.14 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <iostream>
#define x first
#define y second
using namespace std;
const int MAXN = 100005;
const double MAXER = 1e-6;
const char iname[] = "cmap.in",
            oname[] = "cmap.out";
int n;
pair<int, int> sortx[MAXN], sorty[MAXN];
inline long double min(long double d1, long double d2){
    if(d1 < d2)
        return d1;
    return d2;
}
bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.y < b.y)
        return true;
    if(a.y == b.y && a.x <= b.x)
            return true;
    return false;
}

double calcDist(pair<int, int> a, pair<int, int> b){
    return sqrt((int64_t)a.x*a.x + (int64_t)b.x*b.x - (int64_t)2*a.x*b.x +(int64_t)a.y*a.y + (int64_t)b.y*b.y - (int64_t)2*a.y*b.y);

}

long double getD(int lo, int hi){
    if(hi - lo <= 2){
        long double dmin = INFINITY, d;
        for(int i = lo; i <= hi; ++i){
            for(int j = i+1; j <= hi; ++j){
                d = calcDist(sortx[i], sortx[j]);
                if(d < dmin)
                    dmin = d;
            }
        }
        return dmin;
    }
    int mid = (lo+hi)/2;
    long double d1 = getD(lo, mid);
    long double d2 = getD(mid+1, hi);
    long double d = min(d1, d2);
    int centru = sortx[mid].x;
    vector<pair<int, int>> inBanda;
    for(int i = 0; i < n; ++i)
        if(sorty[i].x >= centru - d && sorty[i].x <= centru + d)
            inBanda.push_back(sorty[i]);
    int size = inBanda.size();
    for(int i = 0; i < size; ++i){
        for(int j = i+1; j <= i+7 && j < size; ++j){
            d1 = calcDist(inBanda[i], inBanda[j]);
            if(d1 < d)
                d = d1;
        }
    }
    return d;
}

int main()
{
    freopen(iname, "r", stdin);
    freopen(oname, "w", stdout);
    scanf("%d", &n);
    int a,b;
    for(int i = 0; i < n; ++i){
        scanf("%d %d", &a, &b);
        sortx[i] = make_pair(a,b);
        sorty[i] = make_pair(a,b);
    }
    sort(sortx, sortx+n);
    sort(sorty, sorty+n, cmp);
    double ans = getD(0, n-1);
    cout << fixed;
    cout << setprecision(7) << ans;
    return 0;
}