Pagini recente » Cod sursa (job #398830) | Cod sursa (job #1123184) | Cod sursa (job #1004202) | Cod sursa (job #167970) | Cod sursa (job #1264217)
#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
#define mid (left + right) / 2
const LL INF = 4e18;
struct POINT {
LL x, y;
void read() {
scanf("%lld%d", &x, &y);
}
};
vector <POINT> p;
LL dist (POINT a, POINT b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool cmpX (POINT a, POINT b) {
return a.x < b.x;
}
bool cmpY (POINT a, POINT b) {
return a.y < b.y;
}
LL solve (int left, int right) {
if(right - left + 1 < 2)
return INF;
if(right - left + 1 == 2) {
if(p[left].y > p[right].y)
swap(p[left], p[right]);
return dist(p[left], p[right]);
}
int i, j;
LL res = min(solve(left, mid), solve(mid + 1, right));
vector <POINT> y(right - left + 1);
merge(p.begin() + left, p.begin() + mid + 1, p.begin() + mid + 1, p.begin() + right + 1, y.begin(), cmpY);
for(i = 0; i < y.size(); ++ i)
for(j = i + 1; j < y.size() && j - i <= 8; ++ j)
res = min(res, dist(y[i], y[j]));
return res;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
int i, n;
scanf("%d", &n);
p.resize(n);
for(i = 0; i < n; ++ i)
p[i].read();
sort(p.begin(), p.end(), cmpX);
printf("%lf\n", sqrt(solve(0, n - 1)));
return 0;
}