Pagini recente » Cod sursa (job #2801142) | Cod sursa (job #2572283) | Cod sursa (job #2047447) | Cod sursa (job #3123356) | Cod sursa (job #2072320)
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
int x;
int y;
};
vector <punct> v;
double dist(punct p1, punct p2)
{
return ((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool compare (punct A, punct B)
{
if (A.x == B.x)
return A.y < B.y;
return A.x < B.x;
}
double solve (int li, int ls)
{
if (ls - li == 2)
{
double x = min(dist(v[li], v[li + 1]), dist(v[li], v[li + 2]));
return min(x, dist(v[li + 1], v[li + 2]));
}
else
return dist(v[li], v[li + 1]);
}
double combine(double d_min, int li, int mid, int ls)
{
vector <punct> aux;
for (int i = li; i <= ls; i++)
if (abs(v[mid].x - v[i].x) <= d_min)
aux.push_back(v[i]);
sort(aux.begin(), aux.end(), compare);
for (int i = 0; i < (int)aux.size(); i++)
for (int j = i + 1; j < (int)aux.size(); j++)
d_min = min(d_min, dist(aux[i], aux[j]));
return d_min;
}
double divide (int li, int ls)
{
if (ls - li <= 2)
return solve(li, ls);
int mid = (li + ls)/2;
double d_min = min(divide(li, mid), divide(mid + 1, ls));
d_min = combine(d_min, li, mid, ls);
return d_min;
}
int main()
{
long n;
f >> n;
for (int i = 0; i < n; i++)
{
punct a;
f >> a.x;
f >> a.y;
v.push_back(a);
}
if (n <= 3)
cout << solve(0, n-1);
else
{
sort(v.begin(), v.end(), compare);
g << fixed << setprecision(6) << sqrt(divide(0, n-1));
}
f.close();
g.close();
return 0;
}