Pagini recente » Cod sursa (job #165600) | Cod sursa (job #2073714) | Cod sursa (job #2958769) | Cod sursa (job #2034393) | Cod sursa (job #1718261)
#include <fstream>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
ifstream fin("cmap.in");
FILE *fout = fopen("cmap.out", "w");
using ll = long long;
using pii = pair<int,int>;
#define Nmax 100000
#define INF 1100000000
#define mp make_pair
struct CMPY
{
bool operator() (const pii& p1, const pii& p2) const
{
return p1.second < p2.second;
}
};
pair<int, int> v[Nmax];
set< pair<int, int>, CMPY > S;
set< pair<int, int> >::iterator itBegin, itEnd;
bool CMPX(const pii& p1, const pii& p2)
{
return p1.first < p2.first;
}
double dist(const pii &p1, const pii &p2)
{
double d = 1.0 * (p1.first - p2.first) * (p1.first - p2.first) + 1.0 * (p1.second - p2.second) * (p1.second - p2.second);
return sqrt(d);
}
int main()
{
int i, st, dr, n;
double dmin;
fin >> n;
for (i = 0; i < n; ++i) fin >> v[i].first >> v[i].second;
sort(v, v + n, CMPX);
dmin = INF;
for (st = dr = 0; dr < n; ++dr)
{
// la intrare in set este inclus intervalul [st, dr)
for (; st < dr && 1.0 * (v[dr].first - v[st].first) >= dmin; ++st)
S.erase(v[st]);
itBegin = S.lower_bound(mp(0, v[dr].second - dmin));
itEnd = S.upper_bound(mp(0, v[dr].second + dmin));
for (auto it = itBegin; it != itEnd; ++it)
{
dmin = min(dmin, dist(v[dr], *it));
}
S.insert(v[dr]);
}
fprintf(fout, "%.6f\n", dmin);
return 0;
}