Pagini recente » Cod sursa (job #2114788) | Cod sursa (job #3275836) | Cod sursa (job #2411899) | Cod sursa (job #444947) | Cod sursa (job #2932055)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define ll long long
const ll INF = 4e18;
const int MAXN = 2e5 + 5;
struct Point {
ll x, y;
void read() {
fin >> x >> y;
}
Point operator -(const Point &b) const {
return Point{x - b.x, y - b.y};
}
void operator -=(const Point &b) {
x -= b.x;
y -= b.y;
}
long long operator *(const Point &b) const {
return 1LL * x - b.y - 1LL * y * b.x;
}
} point[MAXN];
bool cmp(Point a, Point b) {
return a.x < b.x;
}
ll dist(Point a, Point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
ll divide(ll st, ll dr) {
// Base case
if(dr - st <= 3) {
ll ans = INF;
for(int i = st; i < dr; i++)
for(int j = i + 1; j <= dr; j++)
ans = min(ans, dist(point[i], point[j]));
return ans;
}
// Divide
ll mid = (st + dr) / 2;
ll ansLeft = divide(st, mid);
ll ansRight = divide(mid + 1, dr);
ll d = min(ansLeft, ansRight);
// Combine
vector<Point> aux;
for(int i = st; i <= dr; i++)
if(abs(point[mid].x - point[i].x) <= d)
aux.push_back({point[i].y, point[i].x});
// Sortam punctele gasite in functie de y
sort(aux.begin(), aux.end(), cmp);
for(int i = 0; i < (int) aux.size(); i++)
for(int j = i + 1; j < (int) aux.size() && j - i < 8; j++)
d = min(d, dist(aux[i], aux[j]));
return d;
}
int main() {
ll n;
fin >> n;
for(int i = 1; i <= n; i++)
point[i].read();
// Sortam punctele in functie de x
sort(point + 1, point + n + 1, cmp);
fout << fixed << setprecision(6) << sqrt(1.0 * divide(1, n));
return 0;
}