Pagini recente » Cod sursa (job #1621151) | Cod sursa (job #627746) | Cod sursa (job #1167636) | Cod sursa (job #2458974) | Cod sursa (job #2058441)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#define inf 9999999
#define MAXN 100500
using namespace std;
struct punct{
long long x, y;
}a[MAXN], b[MAXN];
int n;
bool cmpX(punct c,punct d){
return (c.x < d.x);
}
long long dist(punct c,punct d){
return (c.x - d.x) * (c.x - d.x) + (c.y - d.y) * (c.y - d.y);
}
long long minim(long long a,long long b){
if(a < b)
return a;
return b;
}
long long solve(int st,int dr){
if(dr - st <= 0)
return inf;
else if(dr - st == 1){
if(a[st].y > a[dr].y)
swap(a[st],a[dr]);
return dist(a[st],a[dr]);
}
int mid = (st + dr) >> 1;
long long d = minim(solve(st,mid),solve(mid + 1,dr));
int b_size = 0;
int c1 = st, c2 = mid + 1;
while(c1 <= mid && c2 <= dr){
if(a[c1].y > a[c2].y){
b[b_size] = a[c2];
++b_size;
++c2;
}
else{
b[b_size] = a[c1];
++b_size;
++c1;
}
}
while(c1 <= mid){
b[b_size] = a[c1];
++b_size;
++c1;
}
while(c2 <= dr){
b[b_size] = a[c2];
++b_size;
++c2;
}
for(int i = st;i <= dr; ++i)
a[i] = b[i - st];
double d1 = sqrt(d);
b_size = 0;
for(int i = st;i <= dr; ++i){
if(abs(a[mid].x - a[i].x) < d1){
b[b_size] = a[i];
++b_size;
}
}
int j;
for(int i = 0;i < b_size - 1; ++i)
for(j = i + 1;j <= i + 7 && j < b_size; ++j)
d = min(d,dist(b[i],b[j]));
return d;
}
int main(){
fstream f("cmap.in",ios::in);
fstream g("cmap.out",ios::out);
f >> n;
for(int i = 0;i < n; ++i)
f >> a[i].x >> a[i].y;
sort(a,a + n,cmpX);
double answ = sqrt(solve(0,n - 1));
g << fixed << setprecision(6) << answ;
f.close();
g.close();
return 0;
}