Cod sursa(job #1136138)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 8 martie 2014 20:08:23
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define Inf 4e18

using namespace std;

vector < pair<long long, long long > > X,Y,v(100005);
int N;

void citire() {

    ifstream in("cmap.in");
    int i;
    in>>N;
    X.resize(N);
    Y.resize(N);
    for(i=0;i<N;i++)
        in>>X[i].first>>X[i].second;
    sort(X.begin(),X.end());
    for(i=0;i<N;i++)
        Y[i]=make_pair(X[i].second,X[i].first);
    in.close();

}

long long dist( pair <long long,long long> & A,pair <long long,long long> &B) {
    return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}

long long  divetimp(int st,int dr,vector <pair <long long,long long> > &X,vector <pair<long long,long long> > &Y) {

    if(st>=dr-1)
        return Inf;
    else
        if(dr-st==2) {
            if(X[st].second>X[st+1].second)
                swap(X[st],X[st+1]);
            return dist(X[st],X[st+1]);
        }
    long long best;
    int mij=(st+dr)/2;
    pair<long long, long long > a=X[mij];
    best=min(divetimp(st,mij,X,Y),divetimp(mij,dr,X,Y));

    merge(X.begin() + st, X.begin() + mij, X.begin() + mij, X.begin() + dr, v.begin());
    copy(v.begin(), v.begin() + (dr - st), v.begin() + st);

    int nrelem=0;
    for(int i=st;i<dr;++i)
        if(abs(X[i].second-a.first)<=best)
           v[nrelem++]=Y[i];

    for(int i=0;i<nrelem-1;i++)
        for(int j=i+1;j<nrelem &&(j-i)<8;++j)
           best=min(best,dist(v[i],v[j]));
    return best;

}

void solvenafis(){

    ofstream out("cmap.out");
    out<<fixed<<setprecision(6)<<sqrt((double)divetimp(0,N,X,Y))<<'\n';
    out.close();

}

int main() {

    citire();
    solvenafis();
    return 0;

}