Cod sursa(job #2275286)

Utilizator Wh1plashOvidiu Taralesca Wh1plash Data 2 noiembrie 2018 23:18:29
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
// O(nlogn)

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>

#define x first
#define y second
#define INF 100000000.0
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
typedef pair<int,int> punct;
vector<punct> v,w;
int n;
bool cmpy(punct a, punct b){ return a.y > b.y; }
bool cmpx(punct a, punct b){ return a.x > b.x; }
inline double dist(punct a, punct b){ return (double)sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); }

double divide(int st, int dr){
    int m = (st+dr)/2;
    int 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;
//        for(int i = st; i<=dr; i++){
//            if(mij - dmin <= v[i].y || mij + dmin >= v[i].y ){
//                vnou.push_back(v[i]);
//            }
//        }
        double dmin_banda = INF;
        for(int j=0;j<w.size()-1;j++){
            for(int k=j+1; k<min((int)w.size(),j+8); k++){
                dmin_banda = min(dmin_banda,dist(w[j],w[k]));
            }
        }
        return min(dmin,dmin_banda);

    }
}

int main(){
    in >> n;
    v.resize(n); w.resize(n);
    for(int i=0;i<n;i++) {
        in >> v[i].x >> v[i].y;
        w[i] = v[i];
    }
    sort(v.begin(),v.end(),cmpy);
    sort(w.begin(),w.end(),cmpx);
    out << fixed << setprecision(10) << divide(0,n-1);
    return 0;
}