Pagini recente » Cod sursa (job #1608917) | Cod sursa (job #1729650) | Cod sursa (job #1032934) | Cod sursa (job #1997174) | Cod sursa (job #1268724)
#include <fstream>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
FILE *fout = fopen("cmap.out", "w");
#define Nmax 100000
#define oo 2100000000
#define ll long long
#define mp make_pair
#define dist(a, b) ( 1LL * ((a).first - (b).first) * ((a).first - (b).first) + 1LL * ((a).second - (b).second) * ((a).second - (b).second) )
struct classcomp
{
bool operator() (const pair<int, int>& lhs, const pair<int, int>& rhs) const
{return lhs.second < rhs.second;}
};
bool operator< (const pair<int, int>& lhs, const pair<int, int>& rhs)
{return lhs.second < rhs.second;}
pair<int, int> v[Nmax];
set< pair<int, int>, classcomp > S;
set< pair<int, int> >::iterator it, poz;
bool CMPX(pair<int, int> v1, pair<int, int> v2)
{
return v1.first < v2.first;
}
int main()
{
int i, st, dr, n, gata;
double dmin, aux;
fin >> n;
for(i = 0; i < n; ++i) fin >> v[i].first >> v[i].second;
sort(v, v + n, CMPX);
S.insert(v[0]); S.insert(v[1]);
dmin = sqrt( 1.0 * dist(v[0], v[1]) );
for(st = 0, dr = 2; 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]);
S.insert(v[dr]);
poz = S.find(v[dr]);
if(poz != S.begin())
{
gata = 0;
for(it = poz, --it; it != S.begin() && !gata; --it)
if(v[dr].second - (it -> second) >= dmin) gata = 1;
else
{
aux = sqrt( 1.0 * dist(*it, v[dr]) );
if(aux < dmin) dmin = aux;
}
if(!gata)
{
aux = sqrt( 1.0 * dist(*it, v[dr]) );
if(aux < dmin) dmin = aux;
}
}
gata = 0;
for(it = poz, ++it; it != S.end() && !gata; ++it)
if((it -> second) - v[dr].second >= dmin) gata = 1;
else
{
aux = sqrt( 1.0 * dist(*it, v[dr]) );
if(aux < dmin) dmin = aux;
}
}
fprintf(fout, "%.6f\n", dmin);
return 0;
}