Pagini recente » Cod sursa (job #1104258) | Cod sursa (job #1729363) | Cod sursa (job #1867821) | Cod sursa (job #454442) | Cod sursa (job #1718426)
// Las-Vegas algo, O(n * sqrt(n))?
#include <fstream>
#include <random>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
constexpr int MAX_N = 100000;
constexpr double PI = 6 * asin(.5);
pair <double, double> point[MAX_N];
void rotate_point(pair <double, double> &A, const pair <double, double> &angle) {
A = make_pair(A.first * angle.first - A.second * angle.second,
A.first * angle.second + A.second * angle.first);
}
inline double get_angle() {
uniform_real_distribution <double> angles(0, 2 * PI);
default_random_engine m_engine;
return angles(m_engine);
}
double euclidean_distance(const pair <double, double> &A,
const pair <double, double> &B) {
return sqrt((A.first - B.first) * (A.first - B.first)
+ (A.second - B.second) * (A.second - B.second));
}
int main() {
ifstream cin("cmap.in");
ofstream cout("cmap.out");
cin.tie(0);
ios_base::sync_with_stdio(false);
const double angle = get_angle();
pair <double, double> rotation_matrix = make_pair(cos(angle), sin(angle));
int n; cin >> n;
for (int i = 0; i < n; i += 1) {
int x, y; cin >> x >> y;
point[i] = make_pair(1.0 * x, 1.0 * y);
rotate_point(point[i], rotation_matrix);
}
sort(point, point + n);
double min_dist = 1e30;
pair <int, int> pointer;
for (int i = 1; i < n; i += 1) {
int j = i - 1;
while ((j >= 0) and (point[i].first - point[j].first <= min_dist)) {
const double dist = euclidean_distance(point[i], point[j]);
if (dist < min_dist) {
min_dist = dist;
pointer = {i, j};
}
j = j - 1;
}
}
rotation_matrix = {cos(-angle), sin(-angle)};
rotate_point(point[pointer.first], rotation_matrix);
rotate_point(point[pointer.second], rotation_matrix);
cout.precision(8);
cout.setf(ios::fixed, ios::floatfield);
cout << euclidean_distance(point[pointer.first], point[pointer.second]) << '\n';
cout.close();
return 0;
}