Pagini recente » Cod sursa (job #1739854) | Cod sursa (job #2640571) | Cod sursa (job #2649777) | Cod sursa (job #2962529) | Cod sursa (job #1025829)
#include <cstdio>
#include <algorithm>
#define NMAX 100010
using namespace std;
struct Punct {
int x, y;
}v[NMAX];
int N;
inline bool compareAbscissa(const Punct &p1, const Punct &p2) {
return p1.x < p2.x;
}
inline bool compareOrdinate(const Punct &p1, const Punct &p2) {
return p1.y < p2.y;
}
void input() {
freopen("cmap.in", "r", stdin);
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
scanf("%d %d", &(v[i].x), &(v[i].y));
}
}
double distance(const Punct &p1, const Punct &p2) {
return sqrt(1.0*(p1.x - p2.x)*(p1.x - p2.x) + 1.0*(p1.y - p2.y)*(p1.y - p2.y));
}
double dividescu(const int &left, const int &right) {
if (right - left <= 2) {
double d = 4000000000.0;
for (int i = left; i < right; ++i) {
for (int j = i + 1; j <= right; ++j) {
double dist = distance(v[i], v[j]);
d = min(dist, d);
}
}
//mini-sortare dupa ordonache:
sort(v + left, v + right + 1, compareOrdinate);
return d;
}
const int mid = left + (right - left) / 2;
double d = min(dividescu(left, mid), dividescu(mid + 1, right));
//intercla$are
vector<Punct> temp;
int i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (compareOrdinate(v[i], v[j])) {
temp.push_back(v[i]);
++i;
} else {
temp.push_back(v[j]);
++j;
}
}
while (i <= mid) {
temp.push_back(v[i]);
++i;
}
while (j <= right) {
temp.push_back(v[j]);
++j;
}
int size = right - left + 1;
for (i = 0; i < size; ++i) {
v[i + left] = temp[i];
}
//acum ca le-am interclasat, sa vedem distanta...
for (i = left; i < right; ++i) {
int stop = min(i + 7, right);
for (j = i + 1; j <= stop; ++j) {
d = min(d, distance(v[i], v[j]));
}
}
return d;
}
void solve() {
sort(v, v + N, compareAbscissa);
double d = dividescu(0, N - 1);
freopen("cmap.out", "w", stdout);
printf("%0.6f", d);
}
int main() {
input();
solve();
return 0;
}