Pagini recente » Cod sursa (job #1737428) | Cod sursa (job #2443459) | Cod sursa (job #1366450) | Cod sursa (job #1876647) | Cod sursa (job #2070760)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#define X first
#define Y second
#define NMAX 100001
using namespace std;
typedef long long ll;
typedef pair < ll, ll > point;
point points[NMAX], strip[NMAX];
int n, n_strip;
void read() {
ifstream in("cmap.in");
ll x, y;
in >> n;
for (int i = 1; i <= n; ++i) {
in >> x >> y;
points[i] = make_pair(x, y);
}
in.close();
}
bool compareX(const point& f, const point& s) {
if ((f.X < s.X) || (f.X == s.X && f.Y < s.Y))
return true;
return false;
}
bool compareY(const point& f, const point& s) {
if ((f.Y < s.Y) || (f.Y == s.Y && f.X < s.X))
return true;
return false;
}
inline ll dist(const point& p1, const point& p2) {
return (p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y);
}
ll brute_dist(int left, int right) {
ll best_dist = 0;
for (int i = left; i < right; i++)
for (int j = i + 1; j <= right; j++) {
if (best_dist == 0)
best_dist = dist(points[i], points[j]);
else if (best_dist > dist(points[i], points[j]))
best_dist = dist(points[i], points[j]);
}
return best_dist;
}
ll min_dist_strip(ll d_min) {
ll best_dist = d_min;
sort(strip, strip + n_strip + 1, compareY);
for (int i = 1; i < n_strip; i++)
for (int j = i + 1; j <= n_strip && points[j].Y - points[i].Y < d_min; j++) {
if (best_dist > dist(points[i], points[j]))
best_dist = dist(points[i], points[j]);
}
return best_dist;
}
ll min_dist(int left, int right) {
if (right - left < 4)
return brute_dist(left, right);
else {
int mid = left + (right - left) / 2;
ll d1 = min_dist(left, mid);
ll d2 = min_dist(mid + 1, right);
ll d = min(d1, d2);
n_strip = 0;
for (int i = mid; i >= left; --i)
if (points[mid].X - points[i].X < d)
strip[++n_strip] = points[i];
for (int i = mid + 1; i <= right; i++)
if (points[i].X - points[mid].X < d)
strip[++n_strip] = points[i];
ll d3 = min_dist_strip(d);
return min(d, d3);
}
return 0;
}
int main() {
read();
sort(points, points + n + 1, compareX);
ofstream out("cmap.out");
out << fixed << setprecision(6) << sqrt(min_dist(1, n)) << "\n";
out.close();
return 0;
}