Pagini recente » Cod sursa (job #1126369) | Cod sursa (job #1960370) | Cod sursa (job #2161222) | Cod sursa (job #2462908) | Cod sursa (job #2070962)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include<stdlib.h>
#include<climits>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
vector < pair <long long, long long> > banda(100001), X, Y;//100 001 din textul pb de pe InfoArena
long long distanta(pair <long long, long long> &a,pair <long long, long long> &b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);//las in long long pentru ca voi face radical la sfarsit (sa micsorez timpul de rulare; altfel depaseste testele )
}
/*long long distanta_bruta(pair <long long, long long> &a, int S, int D)
{
long long dist = MAX_N;
for (int i = S; i < D; i++)
for (int j = i + 1; j <= D; j++)
dist = min(dist, distanta(a[i],a[j]));
return dist;
}*/
long long divide(int S, int D)
{
if (S >= D-1)
{
if (S >= D - 1)return LLONG_MAX;
}
else
{
/* if (S - D <= 3)
{
return distanta_bruta(Y,S,D);
}*/
if (D - S == 2)
{
if (Y[S] > Y[S + 1])
swap(Y[S], Y[S + 1]);
return distanta(X[S], X[S + 1]);
}
}
int mij = (S + D) / 2;
long long dist = min(divide(S, mij), divide(mij, D));
merge(Y.begin() + S, Y.begin() + mij, Y.begin() + mij, Y.begin() + D, banda.begin());
copy(banda.begin(), banda.begin() + (D - S), Y.begin() + S);
int k = 0;
for (int i = S; i < D; i++ )
if (abs(Y[i].second - X[mij].first) <= dist)
banda[k ++] = Y[i];
for (int i = 0; i < k - 1; i ++)
{
for (int j = i + 1; j < k && j - i < 8; j ++)
dist = min(dist, distanta(banda[i], banda[j]));
}
return dist;
}
int main()
{
int n;
//citesc datele
f>>n;
X.resize(n),Y.resize(n);
for (int i = 0; i <(int) X.size(); i++)
f >> X[i].first >> X[i].second;
//sortex X si creez Y
sort(X.begin(), X.end());
for (int i = 0; i <(int) X.size(); i++)
Y[i] = make_pair(X[i].second, X[i].first);
g << fixed << setprecision(6) << sqrt(divide(0,X.size())) << "\n";
g.close();
f.close();
return 0;
}