Cod sursa(job #3188586)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 3 ianuarie 2024 13:45:07
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 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);
}
long long C(P a,P b)
{
    return 1LL*(a.first-b.first)*(a.first-b.first)+1LL*(a.second-b.second)*(a.second-b.second);
}
long long D(P s[],int n,long long d)
{
    long long m=d,p;
    int i,j;
    for(sort(s,s+n,B),i=0;i<n-1;++i)
        for(j=i+1;j<n&&s[j].second-s[i].second<m;++j)
            if(p=C(s[i],s[j]),p<m)
                m=p;
    return m;
}
long long E(P a[],int n)
{
    if(n<4) {
        int i,j;
        long long s=1e18,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;
    long long s=E(a,m),t=E(a+m,n-m),d=min(s,t);
    P b=a[m],r[n];
    for(j=i=0;i<n;++i)
        if(abs(a[i].first-b.first)<d)
            r[j++]=a[i];
    return min(d,D(r,j,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)<<sqrt(E(a,n)),0;
}