Pagini recente » Cod sursa (job #1920119) | Cod sursa (job #2295574) | Cod sursa (job #977649) | Cod sursa (job #571729) | Cod sursa (job #1093898)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <complex>
#include <iomanip>
using namespace std;
struct ComparerX {
bool operator()(pair<int, int> a, pair<int, int> b) {
return a.first < b.first || (a.first == b.first && a.second < b.second);
}
};
struct ComparerY {
bool operator()(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
};
class ClosestPoints {
public:
ClosestPoints(vector< pair<int,int> > points) {
this->points = points;
ComparerX c;
sort(points.begin(), points.end(), c);
v = divide(0, points.size()-1);
}
double result() {
return sqrt(1.0 * (double)v);
}
private:
vector<pair<int,int> > points;
long long v;
long long divide(int low, int high) {
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 m = (low+high) / 2;
result = min(result, divide(low, m));
result = min(result, divide(m + 1, high));
vector<pair<int, int> > Y;
for (int i=m; points[m].first - points[i].first <= result && i>=0; --i) Y.push_back(points[i]);
for (int i=m+1; points[i].first - points[m].first <= result && i<points.size(); ++i) Y.push_back(points[i]);
ComparerY comp;
sort(Y.begin(), Y.end(), comp);
for (int i=0; i<Y.size(); ++i) {
for (int j=i+1; j-i <= 7 && j<Y.size(); ++j) {
result = min(result, dist(Y[i], Y[j]));
}
}
return result;
}
long long dist(int x, int y) {
return ((long long)points[x].first - points[y].first) * ((long long)points[x].first - points[y].first) +
((long long)points[x].second - points[y].second) * ((long long)points[x].second - points[y].second);
}
long long dist(pair<int, int> x, pair<int, int> y) {
return ((long long)x.first - y.first) * ((long long)x.first - y.first) +
((long long)x.second - y.second) * ((long long)x.second - 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 << fixed << setprecision(6) << cp.result() << "\n";
return 0;
}