Pagini recente » Cod sursa (job #1032038) | Cod sursa (job #1195189) | Cod sursa (job #1948062) | Cod sursa (job #906707) | Cod sursa (job #1335092)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#define Nmax 100100
#define oo (1 << 30)
using namespace std;
int N;
double Answer;
struct point {double x, y;} PointX[Nmax], PointY[Nmax], Tmp[Nmax];
inline double dist(point A, point B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
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 dist(PointX[left], PointX[right]);
}
int i, j, top, middle = (left + right) >> 1;
double e = min(Dei(left, middle), Dei(middle + 1, right));
i = left;
j = middle + 1;
for(top = left; top <= right; top++)
if((PointY[i].y < PointY[j].y && i <= middle) || j > right)
Tmp[top] = PointY[i++];
else
Tmp[top] = PointY[j++];
for(i = left; i <= right; i++)
PointY[i] = Tmp[i];
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, dist(Tmp[i], Tmp[j]));
return e;
}
void Solve() {
sort(PointX + 1, PointX + N + 1, compareX);
for(int i = 1; i <= N; i++)
PointY[i] = PointX[i];
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;
in.close();
}
void Write() {
ofstream out("cmap.out");
out << fixed << setprecision(10) << Answer << '\n';
out.close();
}
int main() {
Read();
Solve();
Write();
return 0;
}