Pagini recente » Cod sursa (job #2602769) | Cod sursa (job #1941960) | Cod sursa (job #303806) | Cod sursa (job #2446384) | Cod sursa (job #810688)
Cod sursa(job #810688)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <utility>
using namespace std;
typedef long long i64;
const i64 INF = 4e18;
const i64 MAX_N = 100000;
vector<pair<i64, i64> > V(MAX_N), X, Y;
i64 dist(const pair <i64, i64>& a, const pair <i64, i64>& b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
i64 cmap(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(X[left], X[left + 1]);
}
int mid = (left + right)/2;
i64 best = min(cmap(left, mid), cmap(mid, right));
merge(Y.begin() + left, Y.begin() + mid, Y.begin() + mid, Y.begin() + right, V.begin());
copy(V.begin(), V.begin() + (right - left), Y.begin() + left);
int v_size = 0;
for(int i = 0; i < right; ++i)
if (abs(Y[i].second - X[mid].first) <= best)
V[v_size++] = Y[i];
for(int i = 0; i < v_size - 1; ++i)
for(int j = i + 1; j < v_size && j - i < 8; ++j)
best = min(best, dist(V[i], V[j]));
return best;
}
int main()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
int N;
in >> N;
X.resize(N);
Y.resize(N);
for(int i = 0; i < N; ++i)
in >> X[i].first >> X[i].second;
sort(X.begin(), X.end());
for(int i = 0; i < N; ++i)
Y[i] = make_pair(X[i].second, X[i].first);
out << fixed << sqrt(cmap(0, N));
in.close();
out.close();
return 0;
}