Pagini recente » Cod sursa (job #2029103) | Cod sursa (job #877957) | Cod sursa (job #787400) | Cod sursa (job #494400) | Cod sursa (job #1093882)
#include <vector>
#include <fstream>
#include <algorithm>
#include <complex>
#include <iomanip>
using namespace std;
struct Comparer {
bool operator()(pair<int, int> a, pair<int, int> b) {
return a.first < b.first || (a.first == b.first && a.second < b.second);
}
};
class ClosestPoints {
public:
ClosestPoints(vector< pair<int,int> > points) {
this->points = points;
Comparer c;
sort(points.begin(), points.end(), c);
v = divide(0, points.size()-1, p1, p2);
}
float result() {
return sqrt(v);
}
private:
vector<pair<int,int> > points;
long long v;
int p1, p2;
long long divide(int low, int high, int& p1, int& p2) {
long long result = 0x7fffffffLL * 0x7fffffffLL;
if (high-low+1 <= 3) {
for (int i=low; i<high; ++i)
for (int j=i+1; j<=high; ++j) {
result = min(result, dist(i, j));
}
return result;
}
int p1l, p2l, p1r, p2r;
int m = (low+high) / 2;
result = min(result, divide(low, m, p1l, p2l));
result = min(result, divide(m + 1, high, p1r, p2r));
int ll = m,
hh = m;
int x = points[m].first;
while (points[m].first - points[ll].first < x && ll > 0) ll--;
while (points[hh].first - points[m].first < x && hh < high) hh++;
for (int i=ll; i<hh; ++i) {
for (int j=i+1; j-i <= 7 && j<=hh; ++j) {
result = min(result, dist(i, j));
}
}
return result;
}
long long dist(int x, int y) {
return (points[x].first - points[y].first) * (points[x].first - points[y].first) +
(points[x].second - points[y].second) * (points[x].second - points[y].second);
}
};
int main() {
ifstream in("cmap.in");
ofstream out("cmap.out");
vector<pair<int, int> > points;
int N;
in >> N;
for (int i=0; i<N; ++i) {
int x, y;
in >> x >> y;
points.push_back(make_pair(x, y));
}
ClosestPoints cp(points);
out << setprecision(9) << cp.result() << "\n";
return 0;
}