Pagini recente » Cod sursa (job #2023068) | Cod sursa (job #63863) | Cod sursa (job #1735520) | Cod sursa (job #1869743) | Cod sursa (job #1681539)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <limits.h>
#include <cmath>
#include <iomanip>
using namespace std;
struct pct {
long long x;
long long y;
};
ifstream in("cmap.in");
ofstream out("cmap.out");
long long dist;
pct v[100003];
vector<pct> tmp;
vector<pct>::iterator it;
vector<pct>::iterator it2;
bool cmp(pct a, pct b) {
if(a.x != b.x)
return a.x < b.x;
else
return a.y < b.y;
}
bool cmp2(pct a, pct b) {
if(a.y != b.y)
return a.y < b.y;
else
return a.x < b.x;
}
inline long long distP(pct a, pct b) {
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long long sm(int st, int dr) {
if(dr == st+1)
return distP(v[st], v[dr]);
int mid = (st+dr)/2;
long long minX = min(sm(st, mid), sm(mid, dr));
int line = (v[st].x+v[dr].x)/2;
tmp.clear();
for(int i = st; i <= dr; i++)
if(abs(v[i].x-line) < minX)
tmp.push_back(v[i]);
sort(tmp.begin(), tmp.end(), cmp2);
for(it = tmp.begin(); it != tmp.end(); it++)
for(it2 = it+1; it2 != tmp.end(); it2++)
minX = min(minX, distP(*it, *it2));
return minX;
}
int main() {
int n;
in >> n;
for(int i = 1; i <= n; i++)
in >> v[i].x >> v[i].y;
sort(v, v+n, cmp);
out << fixed << setprecision(6) << sqrt(sm(1, n));
return 0;
}