Pagini recente » Cod sursa (job #893329) | Cod sursa (job #1423818) | Monitorul de evaluare | Cod sursa (job #1847914) | Cod sursa (job #721269)
Cod sursa(job #721269)
// Implementare folosind un algoritm de baleiere
// 100 de puncte
#include<fstream>
#include<list>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
typedef long long LL;
typedef pair<LL,LL> Punct;
Punct v[100100];
list <Punct> sweepline;
LL sol=1000000000000000001LL;
inline void Citire()
{
int i;
Punct A;
ifstream fin("cmap.in");
fin>>n;
for(i=1;i<=n;i++)
{
fin>>A.first>>A.second;
v[i]=A;
}
fin.close();
}
inline LL Dist(Punct A,Punct B)
{
return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}
void Rezolvare()
{
int i;
Punct curent,urmator;
list <Punct>::iterator it;
LL dist;
sort(v+1,v+n+1);
for(i=1;i<=n;i++)
{
curent=v[i];
for(it=sweepline.begin();it!=sweepline.end();it++)
{
urmator=*it;
dist=Dist(curent,urmator);
if(curent.first-urmator.first>=sol)
{
sweepline.erase(it);
}
else
{
sol=min(sol,dist);
}
}
sweepline.push_back(curent);
}
}
inline void Afisare()
{
freopen("cmap.out","w",stdout);
printf("%.6lf\n",sqrt((double)sol));
}
int main()
{
Citire();
Rezolvare();
Afisare();
return 0;
}