Cod sursa(job #2496480)

Utilizator ArdeleanOficialAlexandru ArdeleanOficial Data 20 noiembrie 2019 22:06:22
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <set>
#include <iomanip>
#include <random>
#include <ctime>
#include <tuple>

using namespace std;

mt19937 rnd((long long)(new char));

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const int N = 1e5 + 7;
const double INF = 1e10;

struct Point {
    double x, y;

    bool operator < (const Point &a) const {
        if (x == a.x)
            return y < a.y;
        return x < a.x;
    }
};

double dist(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

Point v[N];

int main()
{
    clock_t start(clock());
    int n;
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;
    sort(v, v + n);
    int st(1);
    double mind(INF);

    while ((double)(clock() - start) / CLOCKS_PER_SEC < 0.32) {
         double angle = rnd();
        for (int i = 1; i <= n; ++i)
            tie(v[i].x, v[i].y) = make_pair(v[i].x * cos(angle) - v[i].y * sin(angle), v[i].x * sin(angle) + v[i].y * cos(angle));
        sort(v + 1, v + n + 1);
        for (int i = 1; i < n; ++i)
            mind = min(mind, dist(v[i], v[i + 1]));
    }

    fout << fixed << setprecision(7);
    fout << mind;
    return 0;
}