Pagini recente » Cod sursa (job #1356262) | Cod sursa (job #1475286) | Cod sursa (job #338943) | Cod sursa (job #332808) | Cod sursa (job #1909477)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
#define Nmax 100001
#define inf 1e9
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
double u = inf;
pair<int,int> v[Nmax];
bool comp(pair<int,int> a, pair<int,int> b)
{
return a.first<b.first;
}
double dist(pair<int,int> a, pair<int,int> b)
{
return sqrt(((long double)(a.first-b.first) * (a.first-b.first)) + ((long double)(a.second-b.second) * (a.second-b.second)));
}
int ctbU(int x,int st,int dr)
{
int mij;
while (st<=dr)
{
int mij = (st+dr)/2;
if (v[mij].first>=x)
dr = mij-1;
else
st = mij+1;
}
return st;
}
int ctbD(int x,int st,int dr)
{
int mij;
while (st<=dr)
{
int mij = (st+dr)/2;
if (v[mij].first>x)
dr = mij-1;
else
st = mij+1;
}
return dr;
}
bool comp2(pair<int,int> a,pair<int,int> b)
{
return a.second<b.second;
}
double divide(int a,int b)
{
if (b-a+1==1)
{
return inf;
}
double u1 = divide(a,(a+b)/2);
double u2 = divide((a+b)/2+1,b);
u = min(u,min(u1,u2));
vector<pair<int,int> > A,B;
for (int i=(a+b)/2;v[i].first>=v[(a+b)/2].first - u && i>=a;i--)
A.push_back(v[i]);
sort(A.begin(),A.end(),comp2);
for (int i=(a+b)/2+1;v[i].first<=v[(a+b)/2+1].first + u && i<=b;i++)
B.push_back(v[i]);
sort(B.begin(),B.end(),comp2);
int i1 = 0,i2 = 0;
while (i1<A.size() && i2<B.size())
{
if (i2>1)
u = min(u,dist(A[i1],B[i2-2]));
if (i2>0)
u = min(u,dist(A[i1],B[i2-1]));
u = min(u,dist(A[i1],B[i2]));
if (i2<B.size()-1)
u = min(u,dist(A[i1],B[i2+1]));
if (i2<B.size()-2)
u = min(u,dist(A[i1],B[i2+2]));
if (A[i1].second<B[i2].second)
i1++;
else
i2++;
}
A.clear();
B.clear();
return u;
}
int main()
{
f>>n;
for (int i=1;i<=n;i++)
{
int x,y;
f>>x>>y;
v[i] = make_pair(x,y);
}
sort(v+1,v+n+1,comp);
divide(1,n);
g<<fixed;
g<<setprecision(7)<<u;
return 0;
}