Pagini recente » Cod sursa (job #3220597) | Cod sursa (job #976324) | Cod sursa (job #2550108) | Cod sursa (job #2139000) | Cod sursa (job #1157300)
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;
#define NMAX 100001
#define INF 1LL<<40
#define x first
#define y second
vector < pair < int , int > > v,aux1,aux2;
inline double dist(pair < int , int > a, pair < int , int > b)
{
return sqrtl(0LL+1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y));
}
double solve(int a, int b)
{
if(a+1==b)
return dist(v[a],v[b]);
if(a+2==b)
return min(dist(v[a+1],v[a+2]),min(dist(v[a],v[a+1]),dist(v[a],v[a+2])));
int mij;
mij=(a+b)/2;
double d1 = solve(a,mij);
double d2 = solve(mij,b);
double sol;
int i,j,k,n1,n2;
d1 = min(d1,d2);
sol = INF;
for(i=mij;i<=b && (double)(v[i].x-v[mij].x)<=d1;i++)
aux2.push_back(make_pair(v[i].y,v[i].x));
for(i=mij;i>=a && (double)(v[mij].x-v[i].x)<=d1;i--)
aux1.push_back(make_pair(v[i].y,v[i].x));
sort(aux1.begin(),aux1.end());
sort(aux2.begin(),aux2.end());
n1=aux1.size()-1;
n2=aux2.size()-1;
j=0;
for(i=0;i<=n1;i++) {
while(j<=n2 && (double)(aux2[j].x+d1)<aux1[i].x)
j++;
for(k=j;k<=n2 && (k-j)<=7;k++)
if(aux1[i].x!=aux2[k].x || aux1[i].y!=aux2[k].y)
sol=min(sol,dist(aux1[i],aux2[k]));
}
aux1.clear();
aux2.clear();
return min(sol,d1);
}
int main ()
{
int i,n;
ifstream f("cmap.in");
ofstream g("cmap.out");
f>>n;
v.resize(n+1);
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
f.close();
sort(v.begin()+1,v.end());
g<<fixed;
g<<setprecision(6)<<solve(1,n)<<'\n';
g.close();
return 0;
}