Pagini recente » Cod sursa (job #1071208) | Cod sursa (job #2269534) | Cod sursa (job #953773) | Cod sursa (job #395559) | Cod sursa (job #1335078)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#define Nmax 100100
#define oo (1 << 30)
#define distance(a, b) sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y))
using namespace std;
int N;
double Answer;
struct point {int x, y;} PointX[Nmax], PointY[Nmax], Tmp[Nmax];
bool compareX(point A, point B) {
return A.x < B.x;
}
bool compareY(point A, point B) {
return A.y < B.y;
}
double Dei(int left, int right) {
if(left == right)
return oo;
else
if(left + 1 == right) {
if(PointY[left].y > PointY[right].y)
swap(PointY[left], PointY[right]);
return distance(PointX[left], PointX[right]);
}
int i, j, top, middle = (left + right) >> 1;
double e = min(Dei(left, middle), Dei(middle + 1, right));
merge(PointY + left, PointY + middle, PointY + middle + 1, PointY + right, Tmp, compareY);
copy(Tmp, Tmp + (right - left), PointY + left);
top = 0;
for(i = left; i <= right; i++)
if(abs(PointY[i].x - PointX[middle].x) < e)
Tmp[++top] = PointY[i];
for(i = 1; i < top; i++)
for(j = i + 1; j - i <= 8 && j <= top; j++)
e = min(e, distance(Tmp[i], Tmp[j]));
return e;
}
void Solve() {
sort(PointX + 1, PointX + N + 1, compareX);
Answer = Dei(1, N);
}
void Read() {
ifstream in("cmap.in");
in >> N;
for(int i = 1; i <= N; i++) {
in >> PointX[i].x >> PointX[i].y;
PointY[i].x = PointX[i].x;
PointY[i].y = PointX[i].y;
}
in.close();
}
void Write() {
ofstream out("cmap.out");
out << fixed << setprecision(10) << Answer << '\n';
out.close();
}
int main() {
Read();
Solve();
Write();
return 0;
}