Pagini recente » Cod sursa (job #94095) | Cod sursa (job #2852245) | Cod sursa (job #370653) | Cod sursa (job #380396) | Cod sursa (job #415606)
Cod sursa(job #415606)
using namespace std;
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cmath>
#define mk make_pair
#define x first
#define y second
const int MAX_N = 100007;
typedef long long ll;
const ll oo = 4e18;
vector<pair<ll, ll> > X, Y, V(MAX_N);
int N;
inline ll dist ( pair<ll, ll> A, pair<ll, ll> B)
{
return (A.x - B.x)*(A.x - B.x) + ( A.y - B.y )*(A.y - B.y);
}
ll DivideEtImpera(int st, int dr, vector<pair<ll, ll> >& X, vector<pair<ll, ll> >& Y)
{
int i,j;
if( st >= dr - 1 ) return oo; // unul sau zero elemente
else if( st == dr - 2) // 2 elemente
{
if( Y[st] > Y[st+1] ) swap(Y[st], Y[st+1]); //sortez
return dist(X[st], X[st+1]);
}
int m = (st+dr)>>1, k = 0;
ll bst = min ( DivideEtImpera(st, m, X, Y), DivideEtImpera(m, dr, X, Y ) );
merge(Y.begin() + st, Y.begin() + m, Y.begin() + m, Y.begin() + dr, V.begin() );
copy( V.begin(), V.begin() + (dr - st), Y.begin() + st);
for(i = st; i < dr; ++i) if( abs(Y[i].y - X[m].x) <= bst ) V[k++] = Y[i];
for(i = 0; i < k; ++i)
for(j = i + 1; j < k && j-i < 8; ++j)
bst = min(bst, dist( V[i], V[j] ));
return bst;
}
int main()
{
ifstream in("cmap.in"); ofstream out("cmap.out");
in>>N;
int i, j, x, y;
for(i = 1; i <= N; ++i)
{
in>>x>>y;
X.push_back(mk(x,y));
}
sort(X.begin(), X.end());
for(i = 0; i < X.size(); ++i)
Y.push_back(mk(X[i].y, X[i].x));
out << fixed << setprecision(6) << sqrt((double)DivideEtImpera(0, (int) X.size(), X, Y)) << "\n";
return 0;
}