Pagini recente » Cod sursa (job #585541) | Cod sursa (job #2890092) | Cod sursa (job #2054174)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
inline long long sqr(int x) {
return 1LL * x * x;
}
class Point {
public:
int x, y;
Point(){}
Point(int x, int y) {
this->x = x;
this->y = y;
}
friend istream& operator>> (istream& in, Point& a) {
in >> a.x >> a.y;
}
friend bool operator< (const Point a, const Point b) {
return a.x < b.x;
}
friend long long dist(const Point a, const Point b) {
return sqr(a.x - b.x) + sqr(a.y - b.y);
}
};
vector<Point> puncteX, puncteY, middlePoints;
void customMerge(int st, int mid, int dr, int lineX, long long d) {
int i = st, j = mid + 1;
vector<Point> aux;
while (i <= mid && j <= dr) {
if (puncteY[i].y <= puncteY[j].y) {
if (lineX - puncteY[i].x < d)
middlePoints.push_back(puncteY[i]);
aux.push_back(puncteY[i]);
++i;
}
else {
if (puncteY[j].x - lineX < d)
middlePoints.push_back(puncteY[j]);
aux.push_back(puncteY[j]);
++j;
}
}
while (i <= mid) {
if (lineX - puncteY[i].x < d)
middlePoints.push_back(puncteY[i]);
aux.push_back(puncteY[i]);
++i;
}
while (j <= dr) {
if (puncteY[j].x - lineX < d)
middlePoints.push_back(puncteY[j]);
aux.push_back(puncteY[j]);
++j;
}
for (int i = st, j = 0; j < aux.size(); ++i, ++j) {
puncteY[i] = aux[j];
}
}
long long closestPoints(int st, int dr, int t) {
/*
for (int i = 1; i <= t; ++i)
cerr << "\t";
cerr << "Begin: [" << st << ", " << dr << "]\n";
*/
if (st >= dr) {
for (int i = 1; i <= t; ++i)
/* cerr << "\t";
cerr << "End: [" << st << ", " << dr << "] -> " << 1LL * 1e18 << "\n";
*/
return 1LL * 1e18;
}
if (st + 1 == dr) {
if (puncteY[st].y > puncteY[dr].y) {
swap(puncteY[st], puncteY[dr]);
}
/* for (int i = 1; i <= t; ++i)
cerr << "\t";
cerr << "End: [" << st << ", " << dr << "] -> " << dist(puncteX[st], puncteX[dr]) << "\n";
*/
return dist(puncteX[st], puncteX[dr]);
}
int mid = (st + dr) >> 1;
long long d1 = closestPoints(st, mid, t + 1);
long long d2 = closestPoints(mid + 1, dr, t + 1);
long long d = min(d1, d2);
customMerge(st, mid, dr, puncteX[mid].x, d);
for (int i = 0; i < middlePoints.size(); ++i) {
for (int j = i + 1; j < middlePoints.size(); ++j) {
d = min(d, dist(middlePoints[i], middlePoints[j]));
}
}
middlePoints.clear();
/*
for (int i = 1; i <= t; ++i)
cerr << "\t";
cerr << "End: [" << st << ", " << dr << "] -> " << d << "\n";
*/
return d;
}
int main() {
int n;
fin >> n;
puncteX.resize(n);
puncteY.resize(n);
for (int i = 0; i < n; ++i) {
fin >> puncteX[i];
puncteY[i] = puncteX[i];
}
sort(puncteX.begin(), puncteX.end());
fout << fixed << setprecision(7) << sqrt(closestPoints(1, n, 0));
return 0;
}