Pagini recente » Cod sursa (job #39675) | Cod sursa (job #1559684) | Cod sursa (job #1662014) | Cod sursa (job #2788497) | Cod sursa (job #3277633)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
const int NMAX = 1e5;
int n;
pair<int, int> puncte[1 + NMAX];
vector<int> listaPuncteApropiate;
double distEuclid(int index0, int index1)
{
long long distOX = (long long)puncte[index0].first - (long long)puncte[index1].first;
long long distOY = (long long)puncte[index0].second - (long long)puncte[index1].second;
return sqrt((double)(distOX * distOX + distOY * distOY));
}
pair<double, vector<int>> distMinRec(int st, int dr)
{
if (dr - st + 1 <= 3)
{
double sol = distEuclid(st, st + 1); /// Ca sa nu folosim o constanta INF.
vector<int> sortareY;
if (dr - st + 1 == 2)
{
sol = min(sol, distEuclid(st, st + 1));
if (puncte[st].second < puncte[st + 1].second)
{
sortareY.push_back(st);
sortareY.push_back(st + 1);
}
else
{
sortareY.push_back(st + 1);
sortareY.push_back(st);
}
}
else /// Este sigur 3.
{
sol = min(sol,
min(distEuclid(st, st + 1),
min(distEuclid(st, st + 2),
distEuclid(st + 1, st + 2)
)));
sortareY.push_back(st);
sortareY.push_back(st + 1);
sortareY.push_back(st + 2);
if (puncte[st].second > puncte[st + 1].second)
swap(sortareY[0], sortareY[1]);
if (puncte[st + 1].second > puncte[st + 2].second)
swap(sortareY[1], sortareY[2]);
if (puncte[st].second > puncte[st + 1].second)
swap(sortareY[0], sortareY[1]);
}
return make_pair(sol, sortareY);
}
int mij = (st + dr) / 2;
pair<double, vector<int>> solSt = distMinRec(st, mij);
pair<double, vector<int>> solDr = distMinRec(mij + 1, dr);
double distMinStDr = min(solSt.first, solDr.first);
/// Etapa de Combinare
vector<int> sortareOY;
int indexSortSt = 0;
int indexSortDr = 0;
while (indexSortSt < solSt.second.size() && indexSortDr < solDr.second.size())
{
if (puncte[solSt.second[indexSortSt]].second < puncte[solDr.second[indexSortDr]].second)
{
sortareOY.push_back(solSt.second[indexSortSt]);
++indexSortSt;
}
else
{
sortareOY.push_back(solDr.second[indexSortDr]);
++indexSortDr;
}
}
while (indexSortSt < solSt.second.size())
{
sortareOY.push_back(solSt.second[indexSortSt]);
++indexSortSt;
}
while (indexSortDr < solDr.second.size())
{
sortareOY.push_back(solDr.second[indexSortDr]);
++indexSortDr;
}
listaPuncteApropiate.clear();
for (int i = 0; i < (int)sortareOY.size(); ++i)
if (abs(puncte[sortareOY[i]].first - puncte[mij].first) < distMinStDr)
listaPuncteApropiate.push_back(sortareOY[i]);
/// Final
double sol = distMinStDr;
for (int i = 0; i < (int)listaPuncteApropiate.size(); ++i)
for (int j = i + 1; j <= min(i + 7, (int)listaPuncteApropiate.size() - 1); ++j)
sol = min(sol, distEuclid(listaPuncteApropiate[i], listaPuncteApropiate[j]));
return make_pair(sol, sortareOY);
}
int main()
{
ios_base::sync_with_stdio(false);
ifstream in("cmap.in");
ofstream out("cmap.out");
in.tie(nullptr);
out.tie(nullptr);
in >> n;
for (int i = 1; i <= n; ++i)
in >> puncte[i].first >> puncte[i].second;
sort(puncte + 1, puncte + 1 + n);
out << setprecision(6) << fixed << distMinRec(1, n).first << '\n';
in.close();
out.close();
return 0;
}