Cod sursa(job #3188592)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 3 ianuarie 2024 14:06:38
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include<bits/stdc++.h>
using namespace std;
ifstream F("cmap.in");
ofstream G("cmap.out");
#define P pair<int,int>
P a[100000];
int i,n;
bool A(P a,P b)
{
    return a.first<b.first||(a.first==b.first&&a.second<b.second);
}
bool B(P a,P b)
{
    return a.second<b.second||(a.second==b.second&&a.first<b.first);
}
double C(P a,P b)
{
    return sqrt(1LL*(a.first-b.first)*(a.first-b.first)+1LL*(a.second-b.second)*(a.second-b.second));
}
double E(P a[],int n)
{
    if(n<4) {
        int i,j;
        double s=1e19,t;
        for(i=0;i<n-1;++i)
            for(j=i+1;j<n;++j)
                if(t=C(a[i],a[j]),t<s)
                    s=t;
        return s;
    }
    int m=n/2,i,j,k;
    double d=min(E(a,m),E(a+m,n-m)),e;
    P b=a[m],r[n];
    for(k=i=0;i<n;++i)
        if(abs(a[i].first-b.first)<d)
            r[k++]=a[i];
    for(sort(r,r+k,B),i=0;i<k-1;++i)
        for(j=i+1;j<k&&r[j].second-r[i].second<d;++j)
            if(e=C(r[i],r[j]),e<d)
                d=e;
    return d;
}
int main()
{
    for(F>>n;i<n;F>>a[i].first>>a[i].second,++i);
    return sort(a,a+n,A),G<<fixed<<setprecision(6)<<E(a,n),0;
}