Pagini recente » Cod sursa (job #535085) | Cod sursa (job #1966578) | Cod sursa (job #2409407) | Borderou de evaluare (job #2793670) | Cod sursa (job #3277622)
#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;
int calculareIndexSt(int st, int mij, double distMinStDr)
{
int stCautBin = st;
int drCautBin = mij;
int sol = -1;
while (stCautBin <= drCautBin)
{
int mijCautBin = (stCautBin + drCautBin) / 2;
if (puncte[mij].first - puncte[mijCautBin].first <= distMinStDr)
{
sol = mijCautBin;
drCautBin = mijCautBin - 1;
}
else
{
stCautBin = mijCautBin + 1;
}
}
if (sol == -1)
sol = mij + 1;
return sol;
}
int calculareIndexDr(int mij, int dr, double distMinStDr)
{
int stCautBin = mij + 1;
int drCautBin = dr;
int sol = -1;
while (stCautBin <= drCautBin)
{
int mijCautBin = (stCautBin + drCautBin) / 2;
if (puncte[mijCautBin].first - puncte[mij].first <= distMinStDr + 1)
{
sol = mijCautBin;
stCautBin = mijCautBin + 1;
}
else
{
drCautBin = mijCautBin - 1;
}
}
if (sol == -1)
sol = mij;
return sol;
}
void generareListaPuncteApropiate(int st, int dr, double distMinStDr)
{
listaPuncteApropiate.clear();
int mij = (st + dr) / 2;
int indexSt = calculareIndexSt(st, mij, distMinStDr);
int indexDr = calculareIndexDr(mij, dr, distMinStDr);
int indexCrtSt = indexSt;
int indexCrtDr = mij + 1;
while (indexCrtSt <= mij && indexCrtDr <= indexDr)
{
if (puncte[indexCrtSt].first == puncte[indexCrtDr].first)
{
if (puncte[indexCrtSt].second < puncte[indexCrtDr].second)
{
listaPuncteApropiate.push_back(indexCrtSt);
++indexCrtSt;
}
else
{
listaPuncteApropiate.push_back(indexCrtDr);
++indexCrtDr;
}
}
else if (puncte[indexCrtSt].first < puncte[indexCrtDr].first)
{
listaPuncteApropiate.push_back(indexCrtSt);
++indexCrtSt;
}
else
{
listaPuncteApropiate.push_back(indexCrtDr);
++indexCrtDr;
}
}
while (indexCrtSt <= mij)
{
listaPuncteApropiate.push_back(indexCrtSt);
++indexCrtSt;
}
while (indexCrtDr <= indexDr)
{
listaPuncteApropiate.push_back(indexCrtDr);
++indexCrtDr;
}
}
double distEuclid(int index0, int index1)
{
long long distOX = (long long)puncte[index0].first - puncte[index1].first;
long long distOY = (long long)puncte[index0].second - puncte[index1].second;
return sqrt(distOX * distOX + distOY * distOY);
}
double distMinRec(int st, int dr)
{
if (dr - st + 1 <= 3)
{
double sol = distEuclid(st, st + 1); /// Ca sa nu folosim o constanta INF.
for (int i = st; i <= dr; ++i)
{
for (int j = i + 1; j <= dr; ++j)
{
sol = min(sol, distEuclid(i, j));
}
}
return sol;
}
int mij = (st + dr) / 2;
double distMinSt = distMinRec(st, mij);
double distMinDr = distMinRec(mij + 1, dr);
double distMinStDr = min(distMinSt, distMinDr);
/// Etapa de Combinare
generareListaPuncteApropiate(st, dr, distMinStDr);
double sol = distMinStDr;
for (int i = 0; i < 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 sol;
}
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(8) << distMinRec(1, n) << '\n';
in.close();
out.close();
return 0;
}