Cod sursa(job #2776278)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 19 septembrie 2021 10:20:09
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
ifstream B("cmap.in");
ofstream C("cmap.out");
#define F first
#define S second
#define Q long long
#define M 20000000
vector<pair<Q,Q>> v,x,y;
int n,i,q=-1;
#define D(a,b) ((a.F-b.F)*(a.F-b.F)+(a.S-b.S)*(a.S-b.S))
char u[M];
long long A()
{
  	Q s=0,b=1;
  	q++;
  	if(u[q]==45)
        b=-1,++q;
  	for(;u[q]>47;++q)
  		s=s*10+u[q]-48;
  	return s*b;
}
long long G(int s,int d)
{
    if(d-s<2)
        return 4e18;
    if(d-s==2) {
        if(y[s]>y[s+1])
            swap(y[s],y[s+1]);
        return D(x[s],x[s+1]);
    }
    int m=(s+d)/2,e=0,i,j;
    Q b=min(G(s,m),G(m,d));
    for(sort(y.begin()+s,y.begin()+d),i=s;i<d;++i)
		if(abs(y[i].S-x[m].F)<=b)
        	v[e++]=y[i];
    for(i=0;i<e-1;++i)
        for(j=i+1;j<e&&j-i<8;++j)
            b=min(b,D(v[i],v[j]));
    return b;
}
int main()
{
	B.read(u,M),n=A(),x.resize(n),y.resize(n),v.resize(n);
    for(i=0;i<n;++i)
    	x[i].F=A(),x[i].S=A();
    for(sort(x.begin(),x.end()),i=0;i<n;++i)
        y[i]=make_pair(x[i].S,x[i].F);
    C<<setprecision(6)<<fixed<<sqrt(G(0,n));
    return 0;
}