Pagini recente » Cod sursa (job #2370114) | Cod sursa (job #2364074) | Cod sursa (job #1617700) | Cod sursa (job #489867) | Cod sursa (job #3235092)
#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const string OUT[2]{ "NO", "YES" };
const string out[2]{ "No", "Yes" };
#define all(a) a.begin(), a.end()
#define OK() cerr << "OK until line " << __LINE__ << nl
using ll = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ifstream fin("cmap.in");
ofstream fout("cmap.out");
auto start_time = chrono::high_resolution_clock::now();
double getTime() {
auto end_time = chrono::high_resolution_clock::now();
return chrono::duration<double>(end_time - start_time).count();
}
template<typename T>
int rand(T a, T b) { return uniform_int_distribution<T>(a, b)(rng); }
template<typename T1, typename T2>
bool ckmax(T1& a, T2 b) { return a < b ? a = b, true : false; }
template<typename T1, typename T2>
bool ckmin(T1& a, T2 b) { return a > b ? a = b, true : false; }
struct point {
int x, y;
int index;
point() {
x = y = 0;
}
point(int x, int y) {
this->x = x;
this->y = y;
}
bool operator<(const point& other) {
return x == other.x ? y < other.y : x < other.x;
}
friend double distance(const point& lhs, const point& rhs) {
return sqrt(pow(lhs.x - rhs.x, 2) + pow(lhs.y - rhs.y, 2));
}
};
const int nmax = 5e4;
int n;
point p[nmax + 5];
double min_dist = 1e18;
pair<int, int> best;
point aux[nmax + 5];
struct compare_y {
bool operator()(const point& a, const point& b) {
return a.y < b.y;
}
};
void find_closest_points(int l, int r) {
// bruteforce for small amount of points
if (r - l + 1 <= 3) {
for (int i = l; i <= r; ++i) {
for (int j = i + 1; j <= r; ++j) {
if (ckmin(min_dist, distance(p[i], p[j]))) {
best = make_pair(p[i].index, p[j].index);
}
}
}
// sortam dupa y
sort(p + l, p + r + 1, compare_y());
return;
}
int mid = (l + r) / 2;
// vedem dreapta despartitoare inainte deoarece ordinea punctelor va fi modificata ulterior
int midx = p[mid].x;
// cautam in stanga si in dreapta distanta minima
find_closest_points(l, mid);
find_closest_points(mid + 1, r);
// mergesort -> le avem sortate dupa y (decat sa le sortam din nou)
merge(p + l, p + mid + 1, p + mid + 1, p + r + 1, aux + 1, compare_y());
copy(aux + 1, aux + (r - l + 1) + 1, p + l);
int k = 0;
// cautam punctele din jurul dreptei
for (int i = l; i <= r; ++i) {
if (abs(p[i].x - midx) < min_dist) {
aux[++k] = p[i];
}
}
// vedem daca putem gasi 2 puncte mai apropiate de distanta minima curenta
for (int i = 1; i <= k; ++i) {
for (int j = i + 1; j <= k && aux[j].y - aux[i].y < min_dist; ++j) {
if (ckmin(min_dist, distance(aux[i], aux[j]))) {
best = make_pair(aux[i].index, aux[j].index);
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> p[i].x >> p[i].y;
p[i].index = i;
}
sort(p + 1, p + n + 1);
find_closest_points(1, n);
fout << fixed << setprecision(6) << min_dist;
}