Pagini recente » Istoria paginii preoni-2008/runda-finala/solutii | Istoria paginii runda/oji_simu_2014 | Cod sursa (job #1761067) | Cod sursa (job #1566404) | Cod sursa (job #1237718)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define DIM 100005
#define INF (1LL << 62)
#define infile "cmap.in"
#define outfile "cmap.out"
using namespace std;
ifstream f(infile);
ofstream g(outfile);
pair<long long, long long> x[DIM], y[DIM], z[DIM];
int n;
long long dist(pair<long long, long long> a, pair<long long, long long> b) {
return (a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second);
}
inline long long modul(long long a) {
return (a > 0 ? a : -a);
}
long long solve(int st, int dr) {
if (st == dr)
return INF;
if (dr - st + 1 == 2) {
if (y[st] > y[st + 1]) {
pair<long long, long long> tmp;
tmp = y[st];
y[st] = y[st + 1];
y[st + 1] = tmp;
}
return dist(x[st], x[st + 1]);
}
int mid = (st + dr) / 2;
long long sol = std::min(solve(st, mid), solve(mid + 1, dr));
int i = st, j = mid + 1;
int nn = 0;
while (i <= mid && j <= dr)
if (y[i] <= y[j])
z[++nn] = y[i++];
else
z[++nn] = y[j++];
for (; i <= mid; ++i)
z[++nn] = y[i];
for (; j <= dr; ++j)
z[++nn] = y[j];
for (i = st; i <= dr; ++i)
y[i] = z[i - st + 1];
nn = 0;
for (i = st; i <= dr; ++i)
if (modul(y[i].second - x[mid].first) <= sol)
z[++nn] = y[i];
for (i = 1; i <= nn; ++i)
for (j = i + 1; j <= nn && j <= i + 7; ++j)
sol = std::min(sol, dist(y[i], y[j]));
return sol;
}
int main() {
f >> n;
for (int i = 1; i <= n; ++i)
f >> x[i].first >> x[i].second;
sort(x + 1, x + n + 1);
for (int i = 1; i <= n; ++i) {
y[i].second = x[i].first;
y[i].first = x[i].second;
}
g << setprecision(6) << fixed << sqrt(solve(1, n));
return 0;
}