Pagini recente » Cod sursa (job #1667226) | Cod sursa (job #20710) | Cod sursa (job #2528392) | Cod sursa (job #647294) | Cod sursa (job #2070899)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <cctype>
#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];
point aux[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(point points[], int left, int right) {
ll best_dist = LLONG_MAX;
for (int i = left; i < right; i++)
for (int j = i + 1; j <= right; j++)
best_dist = min(best_dist, dist(points[i], points[j]));
return best_dist;
}
ll min_dist_strip(ll d_min) {
ll best_dist = d_min;
for (int i = 1; i < n_strip; i++)
for (int j = i + 1; j <= n_strip && strip[j].Y - strip[i].Y <= d_min; j++)
best_dist = min(best_dist, dist(strip[i], strip[j]));
return best_dist;
}
void merge(int x1, int y1, int x2, int y2) {
int k = 0;
while (x1 <= y1 && x2 <= y2) {
if (compareY(points[x1], points[x2]))
aux[++k] = points[x1++];
else
aux[++k] = points[x2++];
}
while (x1 <= y1)
aux[++k] = points[x1++];
while (x2 <= y2)
aux[++k] = points[x2++];
}
ll merge_sort(int left, int right) {
if (right - left < 4) {
sort(points + left, points + right + 1, compareY);
return brute_dist(points, left, right);
}
int mid = left + (right - left) / 2;
ll mid_x = points[mid].X;
ll d1 = merge_sort(left, mid);
ll d2 = merge_sort(mid + 1, right);
ll delta = min(d1, d2);
/** **/
merge(left, mid, mid + 1, right);
for (int i = left; i <= right; ++i)
points[i] = aux[i - left + 1];
/** **/
n_strip = 0;
for (int i = left; i <= right; i++)
if (abs(points[i].X - mid_x) <= delta)
strip[++n_strip] = points[i];
ll d3 = min_dist_strip(delta);
return min(delta, d3);
}
int main() {
read();
sort(points, points + n + 1, compareX);
ofstream out("cmap.out");
out << fixed << setprecision(6) << sqrt(merge_sort(1, n)) << "\n";
out.close();
return 0;
}