Pagini recente » Cod sursa (job #1610656) | Cod sursa (job #2411547) | Cod sursa (job #953707) | Cod sursa (job #199438) | Cod sursa (job #2546645)
#include <bits/stdc++.h>
#define NMAX (int)(1e5+4)
#define ft first
#define sd second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long long ll;
typedef pair <ll, ll> pairINT;
ll n,lastX,dmin;
pairINT p[NMAX];
set <pairINT> sweep;
bool upd(int);
void pass(int);
ll dist(pairINT,pairINT);
int main(){
fin>>n;
for(int i=0;i<n;++i)
fin>>p[i].ft>>p[i].sd;
sort(p, p+n);
sweep.insert({p[0].sd, p[0].ft});
lastX=0;
dmin=2e18;
for(int i=1;i<n;++i){
while(upd(i));
sweep.insert({p[i].sd, p[i].ft});
pass(i);
}
fout<<fixed<<setprecision(7)<<sqrt(1.0*dmin);
return 0;
}
void pass(int k){
ll sq=sqrt(1.0 * dmin);
while(p[lastX].ft < p[k].ft - sq){
sweep.erase({p[lastX].sd, p[lastX].ft});
++lastX;
}
}
bool upd(int k){
set <pairINT>::iterator it;
bool ok=0;
ll sq=sqrt(1.0 * dmin);
ll temp = p[k].sd - sq;
it=sweep.lower_bound({temp, 0LL});
while(it != sweep.end()){
temp=dist(p[k], {(*it).sd, (*it).ft});
if(dmin > temp){
dmin=temp;
sq=sqrt(1.0 * dmin);
ok=1;
}
if(temp > dmin)
break;
++it;
}
return ok;
}
ll dist(pairINT A,pairINT B){
return (B.ft - A.ft) * (B.ft - A.ft) +
(B.sd - A.sd) * (B.sd - A.sd);
}