Cod sursa(job #2465389)

Utilizator canmihaiCancescu Mihai canmihai Data 30 septembrie 2019 02:41:54
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb

//draft

#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <climits>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
long long n,maxim=LONG_LONG_MAX;
pair <long long,long long> v[100100],a[100100];
long long calc(pair<long long, long long> a, pair<long long, long long> b) {
    return  abs((a.first - b.first)*(a.first - b.first) +
            (a.second - b.second)*(a.second - b.second));
}
void interclasare(long long st,long long dr, long long mid){
    long long i=st;
    long long j=mid+1;
    long long p=st-1;
    while(i<=mid&&j<=dr){
        if(v[i].second<v[j].second)
            a[++p]=v[i++];
        else
            a[++p]=v[j++];
        for(;i<=mid;i++)
            a[++p]=v[i];
        for(;j<=dr;j++)
            a[++p]=v[j];
        for(long long q=st;q<=dr;q++)
            v[p]=a[q];


    }

}
long long dist(long long st, long long dr){
    /*if(dr-st<=2){
        maxim=0;
        for(long long i=st;i<=dr;i++)
            for(long long j=i+1;j<=dr;j++)
                maxim=min(maxim,calc(v[i],v[j]));
        return maxim;

    }*/
     if (dr-st==1){
        long long aux=calc(v[st],v[dr]);
        interclasare(st,dr,st);
        return aux;
    }
    if (dr-st==2){
        long long aux=min(calc(v[st],v[st+1]), min(calc(v[st],v[st+2]),calc(v[st+1],v[st+2])));
        interclasare(st,st+1,st);
        interclasare(st,dr,st+1);
        return aux;
    }
    long long mid=(dr+st)/2;
    long long ms=dist(st,mid);
    long long md=dist(mid+1,dr);
    interclasare(st,dr,mid);
    maxim=min(ms,md);
    long long c=0;
    for(long long i=st;i<=dr;i++)
        if(abs(v[mid].first-v[i].second)<=maxim)
            a[++c]=v[i];

    for(long long i=st;i<c;i++)
        for(long long j=i+1;j<=i+7&&j<=c;j++)
            maxim=min(maxim,calc(a[i],a[j]));

    return maxim;


}
int main(){
    fin>>n;
    for(long long i=1;i<=n;i++)
        fin>>v[i].first>>v[i].second;
    sort(v+1,v+1+n);
   //  for(long long i=1;i<=n;i++)
    //    fout<<v[i].first<<" "<<v[i].second<<endl;;
    fout<<setprecision(7)<<fixed<<sqrt(dist(1,n));
}