Pagini recente » Cod sursa (job #2935322) | Cod sursa (job #2265224) | Cod sursa (job #59367) | Cod sursa (job #614700) | Cod sursa (job #864704)
Cod sursa(job #864704)
#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
#include <utility>
using namespace std;
#define x first
#define y second
#define MAXN 100005
#define INF 1e17
typedef pair<int, int> Point;
int N;
Point P[MAXN];
inline long long dist(const Point &a, const Point &b) {
return (long long)(a.x - b.x) * (a.x - b.x) + (long long)(a.y - b.y) * (a.y - b.y);
}
long long minDist(int st, int dr, vector<int> &v) {
if(dr - st + 1 <= 3) {
long long ret = INF;
for(int i = st; i < dr; i++)
for(int j = i + 1; j <= dr; j++)
ret = min(ret, dist(P[i], P[j]));
for(int i = st; i <= dr; i++)
v.push_back(i);
for(size_t i = 0; i < v.size(); i++)
for(size_t j = i + 1; j < v.size(); j++)
if(P[v[i]].y > P[v[j]].y) {
int aux = v[i];
v[i] = v[j];
v[j] = aux;
}
return ret;
}
int m = (st + dr) / 2;
vector<int> v1;
long long ret1 = minDist(st, m, v1);
vector<int> v2;
long long ret2 = minDist(m + 1, dr, v2);
long long ret = min(ret1, ret2);
size_t i = 0, j = 0;
while(i < v1.size() && j < v2.size())
if(P[v1[i]].y < P[v2[j]].y)
v.push_back(v1[i++]);
else
v.push_back(v2[j++]);
while(i < v1.size())
v.push_back(v1[i++]);
while(j < v2.size())
v.push_back(v2[j++]);
for(size_t i = 0; i < v.size(); i++)
for(size_t j = i + 1; j <= i + 7 && j < v.size(); j++)
ret = min(ret, dist(P[v[i]], P[v[j]]));
return ret;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out","w", stdout);
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d %d", &P[i].x, &P[i].y);
sort(P, P + N);
vector<int> v;
double ans = sqrt(minDist(0, N - 1, v));
printf("%.6lf\n", ans);
return 0;
}