Pagini recente » Cod sursa (job #2538653) | Cod sursa (job #2670112) | Cod sursa (job #1865754) | Cod sursa (job #1069121) | Cod sursa (job #3155434)
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
const int N = 100010;
const int oo = 1000000010;
typedef pair<int,int> punct;
int n,m=1;
inline punct invers(punct A)
{
swap(A.X,A.Y);
return A;
}
punct P[N];
set<punct> Q;
double dist(punct A,punct B)
{
return sqrt(1.0*(A.X-B.X)*(A.X-B.X)+1.0*(A.Y-B.Y)*(A.Y-B.Y));
}
double d;
int main()
{
f>>n;
for(int i=1; i<=n; i++)
{
int x,y;
f>>x>>y;
P[i]=make_pair(x,y);
}
sort(P+1,P+n+1);
d=dist(P[1],P[2]);
for(int i=1;i<=3;i++)Q.insert(make_pair(oo,oo));
for(int i=1;i<=3;i++)Q.insert(make_pair(-oo,-oo));
Q.insert(invers(P[1]));Q.insert(invers(P[2]));
for(int i=3; i<=n; i++)
{
while(m<i&& P[i].X-P[m].X >= d)
{
Q.erase(invers(P[m]));
m++;
}
punct p=invers(P[i]);
auto here=Q.lower_bound(p);
auto sus=here;
auto jos=here;
while(sus->X-p.X<d)sus++;
while(p.X-jos->X<d)jos--;jos++;
for(auto it=jos;it!=sus;it++)
d=min(d,dist(*it,p));
Q.insert(p);
}
g<<fixed<<setprecision(10)<<d;
return 0;
}