Cod sursa(job #1718424)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 17 iunie 2016 20:00:58
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
// 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);
}

double get_angle(void) {
    uniform_real_distribution <double> angles(0, 2 * PI);
    mt19937 rng; rng.seed(random_device{}());
    return angles(rng);
}

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 = PI * .5;
    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;
}