Cod sursa(job #2492166)

Utilizator andrei.busuiocAndrei Busuioc andrei.busuioc Data 14 noiembrie 2019 02:20:01
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <fstream>

using namespace std;

struct punct{
    long long x,y;
};

vector <punct> P;


long long length(punct a,punct b){
    long long rv;
    rv=( 1LL*(a.x-b.x)*(a.x-b.x) + 1LL*(a.y-b.y)*(a.y-b.y) );
    return rv;
}

bool cmpP(punct a,punct b){
    if(a.x!=b.x)
        return a.x<b.x;
    else
        return a.y<b.y;
}

bool cmpPY(punct a,punct b){
    if(a.y!=b.y)
        return a.y<b.y;
    else
        return a.x<b.x;
}

long long rec(long long s,long long d){
    if(d-s<2)
        return INT_MAX;
    if(d-s==2)
        return length(P[d],P[s]);
    long long mid=s+(d-s)/2;
    long long r=min(rec(s,mid),rec(mid,d));
    if(d-s>2){
        vector <punct> Y;
        punct aux;
        long long x;
        for(unsigned int i=s;i<d;i++){
            aux.x=P[mid].x;
            aux.y=P[i].y;
            x=length(P[i],aux);
            if(x<r)
                Y.push_back(P[i]);
        }
        sort(Y.begin(),Y.end(),cmpPY);
        long long MIN=r;
        for(unsigned int i=0;i<Y.size()-1;i++){
            for(unsigned int j=i+1;j<=i+7 && j<Y.size();j++){
                MIN=min(MIN,length(Y[i],Y[j]));
                /*x=length(Y[i],Y[j]);
                if(x<MIN)
                    MIN=x;*/
            }
        }
        return MIN;
    }
    else
        return r;
}


int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    long long n;
    in>>n;
    punct aux;
    for(unsigned i=0;i<n;i++){
        in>>aux.x>>aux.y;
        P.push_back(aux);
    }
    sort(P.begin(),P.end(),cmpP);
    long long s=0,d=n-1;
    long long r=rec(s,d);
    out<<setprecision(6)<<sqrt(r);

    return 0;
}