Pagini recente » Cod sursa (job #591244) | Cod sursa (job #1884484) | Cod sursa (job #2401425) | Cod sursa (job #127052) | Cod sursa (job #2969153)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long long ll;
struct poll{
ll y,x;
}v[100000];
bool cmp(poll a,poll b){
if(a.y == b.y)return a.x < b.x;
return a.y < b.y;
}
bool cmp2(poll a,poll b){
if(a.x == b.x)return a.y < b.y;
return a.x < b.x;
}
double dist(poll a,poll b){
return sqrt(1ll*abs(a.y - b.y)*abs(a.y - b.y) + 1ll*abs(a.x - b.x)*abs(a.x - b.x));
}
poll v1[100000],v2[100000];
double solve(ll l,ll r){
if(l == r)return 9e18;
ll mij = (l + r)/2;
double d = min(solve(l,mij),solve(mij + 1,r));
//fout<<l<<' '<<r<<' '<<d<<'\n';
ll line = v[mij].y;
ll cnt1 = 0,cnt2 = 0;
for(ll i = l;i <= mij;i++)if(abs(v[i].y - line) <= d)v1[cnt1++] = {v[i].y,v[i].x};
for(ll i = mij + 1;i <= r;i++)if(abs(v[i].y - line) <= d)v2[cnt2++] = {v[i].y,v[i].x};
sort(v1,v1 + cnt1,cmp2);
sort(v2,v2 + cnt2,cmp2);
ll l2 = 0,r2 = -1,od = d;
for(ll i = 0;i < cnt1;i++){
while(r2 != cnt2 - 1 && v2[r2 + 1].x - v1[i].x <= od){
r2++;
};
while(l2 != cnt2 && v1[i].x - v2[l2].x > od){
l2++;
};
for(ll j = l2;j <= r2;j++){
d = min(dist(v2[j],v1[i]),d);
}
}
//fout<<l<<' '<<r<<' '<<d<<'\n';
return d;
}
int main(){
fout<<fixed<<setprecision(6);
ll n,i;
fin>>n;
for(i = 0;i < n;i++){
fin>>v[i].y>>v[i].x;
}
sort(v,v + n,cmp);
/*for(i = 0;i < n;i++){
fout<<v[i].y<<' '<<v[i].x<<'\n';;
}*/
fout<<solve(0,n - 1);
return 0;
}