Pagini recente » Cod sursa (job #2854970) | Cod sursa (job #1554507) | Cod sursa (job #682514) | Cod sursa (job #1855834) | Cod sursa (job #2465389)
//draft
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <climits>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
long long n,maxim=LONG_LONG_MAX;
pair <long long,long long> v[100100],a[100100];
long long calc(pair<long long, long long> a, pair<long long, long long> b) {
return abs((a.first - b.first)*(a.first - b.first) +
(a.second - b.second)*(a.second - b.second));
}
void interclasare(long long st,long long dr, long long mid){
long long i=st;
long long j=mid+1;
long long p=st-1;
while(i<=mid&&j<=dr){
if(v[i].second<v[j].second)
a[++p]=v[i++];
else
a[++p]=v[j++];
for(;i<=mid;i++)
a[++p]=v[i];
for(;j<=dr;j++)
a[++p]=v[j];
for(long long q=st;q<=dr;q++)
v[p]=a[q];
}
}
long long dist(long long st, long long dr){
/*if(dr-st<=2){
maxim=0;
for(long long i=st;i<=dr;i++)
for(long long j=i+1;j<=dr;j++)
maxim=min(maxim,calc(v[i],v[j]));
return maxim;
}*/
if (dr-st==1){
long long aux=calc(v[st],v[dr]);
interclasare(st,dr,st);
return aux;
}
if (dr-st==2){
long long aux=min(calc(v[st],v[st+1]), min(calc(v[st],v[st+2]),calc(v[st+1],v[st+2])));
interclasare(st,st+1,st);
interclasare(st,dr,st+1);
return aux;
}
long long mid=(dr+st)/2;
long long ms=dist(st,mid);
long long md=dist(mid+1,dr);
interclasare(st,dr,mid);
maxim=min(ms,md);
long long c=0;
for(long long i=st;i<=dr;i++)
if(abs(v[mid].first-v[i].second)<=maxim)
a[++c]=v[i];
for(long long i=st;i<c;i++)
for(long long j=i+1;j<=i+7&&j<=c;j++)
maxim=min(maxim,calc(a[i],a[j]));
return maxim;
}
int main(){
fin>>n;
for(long long i=1;i<=n;i++)
fin>>v[i].first>>v[i].second;
sort(v+1,v+1+n);
// for(long long i=1;i<=n;i++)
// fout<<v[i].first<<" "<<v[i].second<<endl;;
fout<<setprecision(7)<<fixed<<sqrt(dist(1,n));
}