Pagini recente » Cod sursa (job #3199696) | Cod sursa (job #197016) | Cod sursa (job #464588) | Cod sursa (job #1869139) | Cod sursa (job #589148)
Cod sursa(job #589148)
#include <cstdio>
#include <utility>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct pct {
int x, y;
};
const int N = 100005;
int n;
pct sorted_x[N], sorted_y[N];
void read() {
scanf("%d", &n);
for(int i = 1; i <= n; ++ i)
scanf("%d%d", &sorted_x[i].x, &sorted_x[i].y);
}
const double INF = 1 << 30;
inline double min(double x, double y) {
return x < y ? x : y;
}
inline double dist(pct x, pct y) {
return sqrt((double)(x.x - y.x) * (x.x - y.x) + (double)(x.y - y.y) * (x.y - y.y));
}
bool comp(const pct &A, const pct &B) {
if (A.x < B.x)
return 1;
if (A.x > B.x)
return 0;
return A.y < B. y;
}
void init() {
sort(sorted_x + 1, sorted_x + n + 1, comp);
for (int i = 1; i <= n; ++ i)
sorted_y[i] = sorted_x[i];
}
double solve(int st, int dr) {
if (st == dr)
return INF;
if (st + 1 == dr) {
if (sorted_y[st].y > sorted_y[st + 1].y)
swap(sorted_y[st], sorted_y[st + 1]);
return dist(sorted_x[st], sorted_x[st + 1]);
}
int mid = (st + dr) / 2;
double best = min(solve(st, mid), solve(mid + 1, dr));
vector <pct> aux_y;
for (int i = st, j = mid + 1; i <= mid || j <= dr;) {
if (i > mid) {
aux_y.push_back(sorted_y[j]);
++ j;
continue;
}
if (j > dr) {
aux_y.push_back(sorted_y[i]);
++ i;
continue;
}
if (sorted_y[i].y > sorted_y[j].y) {
aux_y.push_back(sorted_y[j]);
++ j;
continue;
}
aux_y.push_back(sorted_y[i]);
++ i;
continue;
}
for (int i = 0; i < aux_y.size(); ++ i)
sorted_y[st + i] = aux_y[i];
vector <pct> aux;
for (int i = st; i <= dr; ++ i)
if (sorted_y[i].x >= sorted_x[mid].x - best && sorted_y[i].x <= sorted_x[mid].x + best)
aux.push_back(sorted_y[i]);
for (int i = 0; i < aux.size(); ++ i)
for (int j = i + 1; j < aux.size() && j - i <= 8; ++ j)
if (dist(aux[i], aux[j]) < best)
best = dist(aux[i], aux[j]);
return best;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
read();
init();
printf("%lf\n", solve(1, n));
return 0;
}