Cod sursa(job #2306680)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 22 decembrie 2018 18:48:30
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
struct P
{
	ll x,y;
};
const int N=100001;
int i,n;
P a[N],b[N],d[N];
#define B(a,b) ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
int A(P a,P b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
ll D(int p,int q)
{
    if(q-p<3)
        return B(a[p],a[p+1]);
    int m=(p+q)/2,i,j,k;
    ll c,e,f;
	ll r=(e=D(p,m))<(f=D(m,q))?e:f;
    for(k=i=p,j=m+1;i<=m||j<q;)
    	d[k++]=(j>=q||(i<=m&&a[i].x<a[j].x))?a[i++]:a[j++];
    for(j=0,i=p;i<=q-p;i++)
    	if(abs(d[i].x-a[m].x)<=r)
        	b[++j].x=d[i].y,b[j].y=d[i].x;
    for(i=1;i<j;i++)
    	for(k=i+1;k<=j&&k-i<8;k++)
        	r=r>(c=B(b[i],b[k]))?c:r;
    return r;
}
int main()
{
    freopen("cmap.in","r",stdin),freopen("cmap.out","w",stdout),scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%lld%lld",&a[i].x,&a[i].y);
    sort(a,a+n,A),printf("%.6lf",sqrt(D(0,n)));
}