Pagini recente » Cod sursa (job #2637255) | Cod sursa (job #2396197) | Cod sursa (job #947024) | Cod sursa (job #2019143) | Cod sursa (job #1242986)
#include<fstream>
#include<algorithm>
#include<queue>
#include<cmath>
#define abs(x) ((x>0)?(x):(-(x)))
#define min(a,b) ((a)<(b)?(a):(b))
#define x first
#define y second
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
typedef long long ll;
const int posmax=1<<8;
char buff[posmax]; int pos=posmax;
bool rable(char &c){return ( ('0'<=c && c<='9') || c=='-' );}
void refr(){if(pos>=posmax) in.read(buff,posmax),pos=0;}
void Read(ll &x){
int sm=1;
x=0,refr();
while(!rable(buff[pos])) pos++,refr();
while(rable(buff[pos])){
if(buff[pos]=='-') sm=-sm;
else x=x*10+int(buff[pos])-'0';
pos++;
refr();
}
x*=sm;
}
const int Nmax = 100001;
const ll INF = 0x3f3f3f3f3f3f3f3f;
pair<ll,ll> v[Nmax],temp[Nmax];
queue< pair<ll,ll> > q;
int N;
ll dist(const pair<ll,ll> &a,const pair<ll,ll> &b){
return ( 1LL*(a.x-b.x)*(a.x-b.x) + 1LL*(a.y-b.y)*(a.y-b.y) );
}
ll solve(int st,int dr){
if(st>=dr){
return INF;
}
else{
int mij=(st+dr)/2;
ll midX=v[mij].x;
ll da=solve(st,mij);
ll db=solve(mij+1,dr);
ll sol=min(da,db);
ll nwsol=sol;
int a=st,b=mij+1,k=0;
while(a<=mij && b<=dr){
if(v[a].y<v[b].y) temp[++k]=v[a++];
else temp[++k]=v[b++];
}
while(a<=mij) temp[++k]=v[a++];
while(b<=dr) temp[++k]=v[b++];
for(int i=st;i<=dr;i++){
v[i]=temp[i-st+1];
if(abs(v[i].x-midX) <= sol){
int size=q.size();
for(int j=1;j<=size;j++){
pair<ll,ll> t=q.front();q.pop();
ll dd=dist(v[i],t);
nwsol=min(nwsol,dd);
q.push(t);
}
q.push(v[i]);
if(q.size()>8) q.pop();
}
}
while(!q.empty()) q.pop();
return nwsol;
}
}
int main(){
in>>N;
for(int i=1;i<=N;i++) Read(v[i].x),Read(v[i].y);
sort(v+1,v+N+1);
ll ans = solve(1,N);
out.precision(6);
out<<fixed<<sqrt(ans)<<'\n';
return 0;
}