Pagini recente » Cod sursa (job #1875918) | Cod sursa (job #127246) | Cod sursa (job #2266919) | Cod sursa (job #760977) | Cod sursa (job #1419782)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
using namespace std;
#define int64 long long
#define Pair pair<int64,int64>
#define x first
#define y second
const int Nmax = 100005;
const int inf = (1LL << 31) - 1;
Pair a[Nmax],b[Nmax],v[Nmax];
int N;
int64 dist(Pair A,Pair B) {
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
int64 solve(int l,int r)
{
if(l == r)
return inf;
if(r - l == 1)
return dist(b[r],b[l]);
int mid = (l + r) >> 1;
int64 Ret = min(solve(l,mid),solve(mid+1,r));
merge(b+l,b+mid+1,b+mid+1,b+r+1,v);
copy(v,v+r-l+1,b+l);
int Sz = 0;
for(int i = l; i <= r; i++)
if(abs(b[i].y - a[mid].x) <= Ret)
v[++Sz] = b[i];
for(int i = 1; i < Sz; i++)
for(int j = i + 1; j <= Sz && j - i <= 7; j++)
Ret = min(Ret,dist(v[i],v[j]));
return Ret;
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
fin >> N;
for(int i = 0; i < N; i++) {
int A,B;
fin >> A >> B;
a[i] = make_pair(A,B);
}
sort(a,a+N);
for(int i = 0; i < N; i++)
b[i] = make_pair(a[i].y,a[i].x);
fout << fixed << setprecision(6) << sqrt((double)1LL*solve(0,N-1)) << "\n";
}