Pagini recente » Cod sursa (job #2685484) | Cod sursa (job #1869678) | Cod sursa (job #852081) | Cod sursa (job #3033348) | Cod sursa (job #3214157)
#include <bits/stdc++.h>
using namespace std;
struct punct
{
int l , c;
}a[100001];
long double dist (punct a , punct b)
{
int x = a.l - b.l , y = a.c - b.c;
return sqrt(x * x + y * y);
}
bool cmp1 (punct a , punct b)
{
if(a.c != b.c)
return (a.c < b.c);
return (a.l < b.l);
}
bool cmp (punct a , punct b)
{
if(a.l != b.l)
return a.l < b.l;
return a.c < b.c;
}
long double DIE (int l , int r)
{
if(r - l + 1 <= 3)
{
long double ans = 1e9;
for (int i = l; i <= r; ++i)
for (int j = i + 1; j <= r; ++j)
ans = min(ans , dist(a[i] , a[j]));
return ans;
}
else
{
int m = (l + r) / 2;
long double A = DIE (l , m);
long double B = DIE (m + 1 , r);
long double dMin = min(A , B);
vector <punct> x;
for (int i = l; i <= r; ++i)
if(abs(a[i].l - a[m].l) <= dMin)
x.push_back(a[i]);
sort (x.begin() , x.end() , cmp1);
for(int i = 0; i < (int)x.size(); ++i)
for (int j = i + 1; j < (int)x.size() && j - i + 1 <= 8; ++j)
dMin = min(dMin , dist(x[i] , x[j]));
return dMin;
}
}
int main()
{
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
int N;
fin >> N;
for(int i = 1; i <= N; ++i)
fin >> a[i].l >> a[i].c;
sort(a + 1 , a + N + 1 , cmp);
fout << fixed << setprecision(7) << DIE(1 , N);
}