Pagini recente » Cod sursa (job #493027) | Cod sursa (job #1938172) | Cod sursa (job #2084924) | Cod sursa (job #620161) | Cod sursa (job #1586617)
# include <fstream>
# include <algorithm>
# include <cstring>
# include <cmath>
# include <iomanip>
# define mp make_pair
# define f first
# define s second
# define NR 100005
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
pair <long long, long long> a[NR], aux[NR];
bool cmp (pair <long long, long long> a, pair <long long, long long> b) {
return (a.s < b.s);
}
int i,j,n,m;
long long dist (pair <long long, long long> a, pair <long long, long long> b) {
return (a.f-b.f)*(a.f-b.f) + (a.s-b.s)*(a.s-b.s);
}
long long divide (int st, int dr) {
long long minn=INFINITY;
int i,j,mij;
if (dr-st<=2) {
for (i=st; i<dr; ++i)
for (j=i+1; j<=dr; ++j)
minn=min(minn, dist(a[i], a[j]));
for (i=st; i<dr; ++i)
for (j=i+1; j<=dr; ++j)
if (a[i].s >= a[j].s) swap(a[i], a[j]);
return minn;
}
mij=(st+dr)/2;
divide (st, mij);
divide (mij+1, dr);
// interclasez
merge (a+st, a+mij+1, a+mij+1, a+dr+1, aux+1, cmp);
//copiez
for (i=st; i<=dr; ++i)
a[i]=aux[i-st+1];
//acum verific cu urmatoarele 7 puncte
for (i=st; i<=dr; ++i)
for (j=i+1; j<=i+7 && j<=dr; ++j)
minn=min(minn, dist(a[i], a[j]));
return minn;
}
int main ()
{
f>>n;
for (i=1; i<=n; ++i)
f>>a[i].f>>a[i].s;
sort (a+1, a+n+1);
g<<fixed<<setprecision(6)<<sqrt((double)(divide (1, n)))<<"\n";
return 0;
}