Pagini recente » Cod sursa (job #2808777) | Cod sursa (job #3151116) | Cod sursa (job #1990823) | Cod sursa (job #732173) | Cod sursa (job #631110)
Cod sursa(job #631110)
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>
using namespace std;
const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
#define sz(c) int ((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define FORIT(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define mp make_pair
#define pb push_back
struct Point {
ll x, y;
Point (ll x = 0, ll y = 0) : x(x), y(y) {}
};
double distPointPoint(Point p0, Point p1) {
double dx = p0.x - p1.x;
double dy = p0.y - p1.y;
return sqrt(dx*dx + dy*dy);
}
double closest_pair(vector<Point> &pts) {
vector<pair<double, int> > sorted;
FOR(i, 0, sz(pts)) sorted.push_back(make_pair(pts[i].x, i));
sort(all(sorted));
pair<pii, double> res = make_pair(pii(-1, -1), DBL_MAX);
set<pair<double, int> > active;
int pos = 0;
FOR(i, 0, sz(sorted)) {
double x = sorted[i].first, y = pts[sorted[i].second].y;
while (pos < i && sorted[pos].first < x - res.second) {
active.erase(make_pair(pts[sorted[pos].second].y, sorted[pos].second));
pos++;
}
set<pair<double, int> >::iterator it = active.lower_bound(make_pair(y - res.second, 0));
while (it != active.end() && it->first <= y + res.second) {
double d = distPointPoint(pts[it->second], pts[sorted[i].second]);
if (d < res.second) {
res = make_pair(pii(it->second, sorted[i].second), d);
}
it++;
}
active.insert(make_pair(y, sorted[i].second));
}
return res.second;
}
int main () {
freopen ("cmap.in", "r", stdin);
freopen ("cmap.out", "w", stdout);
int N;
scanf ("%d", &N);
vector<Point> pnts(N);
FOR (i, 0, N) scanf ("%d %d", &pnts[i].x, &pnts[i].y);
printf ("%.9lf\n", closest_pair(pnts));
return 0;
}