Pagini recente » Cod sursa (job #2789608) | Cod sursa (job #3237922) | Cod sursa (job #2262008) | Cod sursa (job #1825873) | Cod sursa (job #2490832)
#include<bits/stdc++.h>
using namespace std;
int const N = 100010;
pair<double,double>puncte[N];
pair<double,double>vec[N];
int n;
double dist( pair<double,double> A,pair<double,double>B)
{
return pow(B.first - A.first,2)+ pow(B.second - A.second,2);
}
double divide(int st, int dr)
{
if(st == dr)
return INT_MAX;
if(st == dr - 1)
return dist(puncte[st], puncte[dr]);
int mij = (st + dr)/2, k = 0;
double x = divide(st, mij);
double y = divide(mij + 1, dr);
double result = min(x, y);
for(int i = st; i <= dr; i++)
if(abs(puncte[i].first - puncte[mij].first) < result)
vec[++k] = {puncte[i].second, puncte[i].first};
sort(vec + 1, vec + k + 1);
for(int i = 1; i < k; i++)
for(int j = i + 1; j <= k && j <= i + 8; j++)
result = min(result, dist(vec[i], vec[j]));
return result;
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
fin >> n;
int x,y;
for(int i=0; i<n; i++)
{
fin >> x >> y;
puncte[i] = make_pair(x, y);
}
sort(puncte, puncte+n);
fout << fixed << setprecision(6) << sqrt(divide(0, n-1)) << "\n";
fin.close();
fout.close();
return 0;
}