Pagini recente » Cod sursa (job #562059) | Cod sursa (job #2127720) | Cod sursa (job #1670779) | Cod sursa (job #1861086) | Cod sursa (job #2974410)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#include <bits/stdc++.h>
#define endl '\n'
#endif
typedef int64_t ll;
const int NMAX = 1e5+5;
const ll INF = 4e18;
struct Point {
int x, y;
bool operator<(const Point &p) {
return y < p.y || (y == p.y && x < p.x);
}
bool operator>(const Point &p) {
return !(*this < p);
}
};
int n;
Point a[NMAX], aux[NMAX], v[NMAX];
ll dist(const Point &a, const Point &b) {
int dx = a.x - b.x;
int dy = a.y - b.y;
return 1ll * dx * dx + 1ll * dy * dy;
}
void read() {
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
}
bool cmp(const Point &a, const Point &b) {
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
void precalc() {
sort(a + 1, a + n + 1, cmp);
}
void merge(int l, int r) {
for (int i = l; i <= r; i++)
aux[i] = a[i];
int mid = (l + r) / 2;
int i = l;
int j = mid + 1;
int last = l;
while (i != mid && j != r) {
if (aux[i] < aux[j])
a[last++] = aux[i], i++;
else
a[last++] = aux[j], j++;
}
for (; i <= mid; i++)
a[last++] = aux[i];
for (; j <= r; j++)
a[last++] = aux[j];
}
ll divide(int l, int r) {
if (l > r)
return INF;
int len = r - l + 1;
if (len <= 3) {
if (a[l] > a[l + 1])
swap(a[l], a[l + 1]);
return dist(a[l], a[l + 1]);
}
int mid = (l + r) / 2;
ll s = min(divide(l, mid), divide(mid + 1, r));
merge(l, r);
int vcnt = 0;
for (int i = l; i <= r; i++)
if (abs(a[i].x - a[mid].x) <= s)
v[++vcnt] = a[i];
for (int i = 1; i <= vcnt; i++)
for (int j = i + 1; j <= vcnt && (j - i) < 8; j++) {
s = min(s, dist(v[i], v[j]));
if (dist(v[i], v[j]) == 0) {
cout << v[i].x << ' ' << v[i].y << endl;
cout << v[j].x << ' ' << v[j].y << endl;
}
}
return s;
}
int main() {
read();
precalc();
fout << setprecision(6) << fixed << sqrt(divide(1, n));
return 0;
}