Cod sursa(job #2275435)

Utilizator Wh1plashOvidiu Taralesca Wh1plash Data 3 noiembrie 2018 10:52:41
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
// O(nlog^2n)

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <cstdio>
#define x first
#define y second
#define INF 10000000000000.0
using namespace std;
//ifstream in("cmap.in");
//ofstream out("cmap.out");
typedef pair<long long,long long> punct;
vector<punct> v,vnou;
long long n;
bool cmpy(punct a, punct b){ return a.y > b.y; }
bool cmpx(punct a, punct b){ return a.x > b.x; }
double dist(punct a, punct b){ return (double)sqrt((long long)(a.x-b.x)*(a.x-b.x) + 0LL + (a.y-b.y)*(a.y-b.y)); }

double divide(long long st, long long dr){
    long long m = (st+dr)/2;
    long long n = dr-st+1;
    if(n == 1) return INF;
    else if( n==2) return dist(v[st],v[dr]);
    else {
        double dmin = min(divide(st,m), divide(m,dr));
        double mij = (double)(v[st].y + v[dr].y)/2;
        vnou.clear();
        for(long long i = st; i<=dr; i++){
            if(mij - dmin <= v[i].y || mij + dmin >= v[i].y ){
                vnou.push_back(v[i]);
            }
        }
        sort(vnou.begin(), vnou.end(), cmpx);
        double dmin_banda = INF;
        if(!vnou.empty()) {
            for (long long j = 0; j < vnou.size() - 1; ++j) {
                for (long long k = j + 1; k < min((long long) vnou.size(), j + 8); k++) {
                    dmin_banda = min(dmin_banda, dist(vnou[j], vnou[k]));
                }
            }
        }
        return min(dmin,dmin_banda);

    }
}

int main(){
    FILE *f, *g;
    f = fopen("cmap.in","r");
    g = fopen("cmap.out","w");
    fscanf(f,"%lld", &n);
    v.resize(n);
    for(long long i=0;i<n;++i)
        fscanf(f,"%lld%lld",&v[i].x,&v[i].y);
    sort(v.begin(),v.end(),cmpy);
    //out << fixed << setprecision(10) << divide(0,n-1);
    double k = divide(0,n-1);
    fprintf(g,"%f", k);
    return 0;
}