Pagini recente » Cod sursa (job #1360397) | Cod sursa (job #1105496) | Cod sursa (job #3121863) | Cod sursa (job #892862) | Cod sursa (job #2661944)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
struct point {
long long x, y;
};
vector<point> points;
int comp (const point &a, const point &b) {
if (a.x < b.x)
return -1;
if (a.x > b.y)
return 1;
if (a.y < b.y)
return -1;
if (a.y > b.y)
return 1;
return 0;
}
long long euclid_distance(const point &a, const point &b) {
return (a.x - b. x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
long long min(long long a, long long b) {
return a < b? a:b;
}
long long divide_et_impera(int left, int right) {
if (right - left <= 2) {
long long res = euclid_distance(points[left], points[right]);
if (right - left == 1)
return res;
return min(res, min(euclid_distance(points[left], points[left + 1]), euclid_distance(points[left+1], points[right])));
}
long long left_res = divide_et_impera(left, (left + right) / 2);
long long right_res = divide_et_impera((left + right) / 2 + 1, right);
long long current_res = min(right_res, left_res);
long long dividing_line = (points[(left + right) / 2].x + points[(left + right) / 2 + 1].x) / 2;
for(int i = (left + right) / 2 - 3; i<= (left + right) / 2; ++i)
if (i >= left && points[i].x > dividing_line - current_res)
for(int j = (left + right) / 2 + 4; j> (left + right) / 2; --j)
if (j <= right && points.size() && points[j].x < dividing_line + current_res)
current_res = min(current_res, euclid_distance(points[i], points[j]));
return current_res;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
int n;
scanf("%d", &n);
points.resize(n);
for(int i=0; i<n; ++i)
scanf("%lld%lld", &points[i].x, &points[i].y);
sort(points.begin(), points.end(), comp);
printf("%.6f\n", sqrt(divide_et_impera(0, n-1)));
return 0;
}