Pagini recente » Cod sursa (job #881794) | Cod sursa (job #2303360) | Cod sursa (job #2359661) | Cod sursa (job #2358570) | Cod sursa (job #1308237)
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <utility>
#define nmax 100005
#define ll long long
using namespace std;
ifstream in("cmap.in");
pair<ll,ll> point[nmax];
pair<ll,ll> V[nmax];
int N;
ll dist(pair<ll, ll> p1, pair<ll, ll> p2) {
return (p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}
ll minimalDistance(int left, int right) {
int mid = (left + right) >> 1;
if (left >= right)
return 1LL << 62;
if (left + 1 == right) {
if ( point[left].second > point[right].second )
swap(point[left], point[right]);
return dist(point[left], point[right]);
}
ll minDist = min(minimalDistance(left, mid), minimalDistance(mid + 1, right));
merge(point + left, point + mid + 1, point + mid + 1, point + right + 1, V);
int nr = 0;
for (int i = left; i <= right; i++) {
if ( abs(point[i].first - point[mid].first) <= minDist)
V[++nr] = point[i];
}
for (int i=1; i<right; i++) {
for (int j=i+1; j<=min(i+5, nr); j++)
minDist = min(minDist, dist(V[j], V[i]));
}
return minDist;
}
int main() {
in >> N;
for (int i=1; i<=N; ++i) {
in >> point[i].first >> point[i].second;
}
sort(point + 1, point + N + 1);
freopen("cmap.out","w",stdout);
printf("%lf", sqrt((double)minimalDistance(1, N)));
return 0;
}