Pagini recente » Cod sursa (job #1423086) | Cod sursa (job #911620) | Cod sursa (job #40196) | Cod sursa (job #315450) | Cod sursa (job #2975774)
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
ifstream in("cmap.in");
ofstream out("cmap.out");
#define cin in
#define cout out
typedef long long ll;
const int MOD = 1e9 + 9;
const ll inf = 1e19;
struct P {
int x, y;
void read() {
cin >> x >> y;
}
bool operator < (P him) {
if(x == him.x) {
return y < him.y;
}
return x < him.x;
}
void write() {
cout << "(" << x << ' ' << y << ")\n";
}
pair<int, int> to_pair() {
return make_pair(x, y);
}
};
ll sqr(ll x) {
return 1LL * x * x;
}
vector<P> points;
int n;
ll dist(const P &a, const P &b) {
return sqr(a.x - b.x) + sqr(a.y - b.y);
}
bool check_dist(ll x1, ll x2, ll square_d) {
return sqr(abs(x2 - x1)) < square_d;
}
ll solve(vector<P> &points, vector<P> &points_y) {
if(points.size() <= 1) {
return inf;
}
vector<P> left, right, left_y, right_y;
int N = points.size();
for(int i = 0; i < N; ++i) {
if(i < N / 2) {
left.push_back(points[i]);
}
else {
right.push_back(points[i]);
}
}
for(int i = 0; i < N; ++i) {
if(points_y[i].to_pair() <= left.back().to_pair()) {
left_y.push_back(points_y[i]);
}
else {
right_y.push_back(points_y[i]);
}
}
ll d1 = solve(left, left_y);
ll d2 = solve(right, right_y);
ll d = min(d1, d2);
vector<P> all;
for(int i = 0; i < N; ++i) {
if(check_dist(points_y[i].x, left.back().x, d)) {
all.push_back(points_y[i]);
}
}
for(int i = 0; i < (int) all.size(); ++i) {
for(int j = i + 1; j < (int) all.size(); ++j) {
if(!check_dist(all[i].y, all[j].y, d)) {
break;
}
d = min(d, dist(all[i], all[j]));
}
}
return d;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
points.resize(n);
for(int i = 0; i < n; ++i) {
points[i].read();
}
vector<P> points_y(points.begin(), points.end());
sort(points.begin(), points.end());
sort(points_y.begin(), points_y.end(), [&] (P a, P b) {
return a.y < b.y;
});
cout << fixed << setprecision(8) << sqrt(solve(points, points_y)) << '\n';
return 0;
}