Pagini recente » Cod sursa (job #522217) | Cod sursa (job #694895) | Cod sursa (job #416514) | Cod sursa (job #2157070) | Cod sursa (job #2490114)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
int n;
struct punct {
double x, y;
} p[100005], p1[100005];
inline bool cmpx(punct A, punct B) {
return A.x < B.x;
}
inline bool cmpy(punct A, punct B) {
return A.y < B.y;
}
double dist(punct A, punct B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
double Dist(int st, int dr) {
int i, j, ct = 0;
int mid = (st + dr) / 2;
if (st == dr - 1)return dist(p[st], p[dr]);
if(st==dr)return 2000000000;
double drx = (p[mid].x + p[mid + 1].x) / 2;
double D = min(Dist(st, mid), Dist(mid + 1, dr));
for (i = st; i <= mid; i++)
if (drx - p[i].x < D) {
ct++;
p1[ct] = p[i];
}
for (i = mid + 1; i <= dr; i++)
if (p[i].x - drx < D) {
ct++;
p1[ct] = p[i];
}
sort(p + 1, p + ct + 1, cmpy);
for (i = 1; i <= ct; i++) {
for (j = i + 1; j <= ct; j++) {
if (p[j].y - p[i].y >= D)break;
D = min(D, dist(p[i], p[j]));
}
}
return D;
}
int main() {
int i;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
fin >> n;
for (i = 1; i <= n; i++)
fin >> p[i].x >> p[i].y;
sort(p + 1, p + n + 1, cmpx);
fout <<setprecision(6)<<fixed<< Dist(1, n);
}