Pagini recente » Cod sursa (job #2878580) | Cod sursa (job #330658) | Cod sursa (job #1423421) | Cod sursa (job #1136882) | Cod sursa (job #1423551)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
#define NMAX 100005
#define lint long long int
#define inf (1ll << 62)
using namespace std;
struct point {
int x, y;
point (int _x = 0, int _y = 0): x(_x), y(_y) {}
};
bool operator< (const point &a, const point &b) {
if (a.y != b.y)
return a.y < b.y;
return a.x < b.x;
}
bool cmp (const point &a, const point &b) {
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
lint dist (const point &a, const point &b) {
return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}
lint closest (vector <point> &points) {
if (points.size() == 1)
return inf;
int middle = (points.size() - 1) / 2;
vector <point> a;
for (int i = 0; i <= middle; i++)
a.push_back(points[i]);
vector <point> b;
for (int i = middle + 1; i < points.size(); i++)
b.push_back(points[i]);
middle = points[middle].x;
lint delta = min(closest(a), closest(b));
merge(a.begin(), a.end(), b.begin(), b.end(), points.begin());
a.clear();
for (int i = 0; i < points.size(); i++)
if (middle - delta <= points[i].x && points[i].x <= middle + delta)
a.push_back(points[i]);
int j;
for (int i = 0; i < a.size(); i++)
for (j = 1; j <= 8 && i + j < a.size(); j++)
if (dist(a[i], a[i + j]) < delta)
delta = dist(a[i], a[i + j]);
return delta;
}
int main()
{
ifstream cin("cmap.in");
ofstream cout("cmap.out");
int n = 0;
vector <point> v;
cin >> n;
int x, y;
while (n--) {
cin >> x >> y;
v.push_back(point(x, y));
}
sort(v.begin(), v.end(), cmp);
cout << fixed << setprecision(6) << sqrt(closest(v)) << '\n';
cin.close();
cout.close();
return 0;
}