Cod sursa(job #2171258)

Utilizator catalinlupCatalin Lupau catalinlup Data 15 martie 2018 11:43:31
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define INFILE "cmap.in"
#define OUTFILE "cmap.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
typedef long long lint;
typedef pair<lint,lint> Point;
const int MAX_N = 100005;
const lint INF = 4e18;

lint dist(Point A, Point B){
    return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}

lint minDist(int st,int dr,vector<Point>&X,vector<Point>&Y){
    if(st>=dr-1)
        return INF;
    if(dr-st==2){
        if(Y[st]>Y[st+1])
            swap(Y[st],Y[st+1]);
        return dist(X[st],X[st+1]);
    }
    int mid=(st+dr)/2;
    lint best=min(minDist(st,mid,X,Y),minDist(mid,dr,X,Y));
    sort(Y.begin()+st,Y.begin()+dr);
    vector<Point> V;
    for(int i=st;i<dr;i++)
        if(abs(Y[i].second-X[mid].first)<=best)
            V.push_back(Y[i]);
    for(int i=0;i<V.size();i++){
        for(int j=i+1;j<V.size()&&(j-i)<8;j++){
            best=min(best,dist(V[i],V[j]));
        }
    }
    return best;
}

int main(){
    int N;
    in>>N;
    vector<Point> X;
    vector<Point> Y;
    for(int i=1;i<=N;i++){
        int x,y;
        in>>x>>y;
        X.push_back({x,y});
    }
    sort(X.begin(),X.end());
    for(auto x:X){
        Y.push_back({x.second,x.first});
    }
    out<<fixed<<setprecision(6)<<sqrt(minDist(0,X.size(),X,Y));
    return 0;
}