Pagini recente » Cod sursa (job #213127) | Cod sursa (job #3199578) | Cod sursa (job #2941847) | Cod sursa (job #2553093) | Cod sursa (job #650453)
Cod sursa(job #650453)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
#define x first
#define y second
typedef long long int64;
typedef pair<int64, int64> point;
const int maxn = 100100;
const int64 inf = 1e18;
vector<point> x, y;
int n;
int64 dist(const point& a, const point& b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int64 find(int left, int right)
{
if (right - left <= 1) {
return inf;
}
if (right - left == 2) {
if (y[left] > y[left + 1]) {
swap(y[left], y[left + 1]);
}
return dist(y[left], y[left + 1]);
}
int mdl = (left + right) >> 1;
int64 s = min(find(left, mdl), find(mdl, right));
vector<point> v(right - left);
merge(y.begin() + left, y.begin() + mdl, y.begin() + mdl, y.begin() + right, v.begin());
copy(v.begin(), v.end(), y.begin() + left);
v.clear();
for (int i = left; i < right; ++i) {
if (abs(y[i].y - x[mdl].x) <= s) {
v.push_back(y[i]);
}
}
for (int i = 0; i < (int)v.size() - 1; ++i) {
for (int j = i + 1; j < min((int)v.size(), i + 8); ++j) {
s = min(s, dist(v[i], v[j]));
}
}
return s;
}
int main()
{
FILE* fin = fopen("cmap.in", "r");
FILE* fout = fopen("cmap.out", "w");
fscanf(fin, "%d\n", &n);
x.resize(n);
y.resize(n);
for (int i = 0; i < n; ++i) {
fscanf(fin, "%d %d\n", &x[i].x, &x[i].y);
}
sort(x.begin(), x.end());
copy(x.begin(), x.end(), y.begin());
printf("%.6lf", sqrt((long double)find(0, n)));
fclose(fin);
fclose(fout);
return 0;
}