Cod sursa(job #2969198)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 22 ianuarie 2023 18:38:18
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

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

const double PI = 4 * atan(1);
const int INF = 2e9;

struct Point {
    double x, y;

    Point() {}
    Point(int x, int y) : x(x), y(y) {}
    Point(double x, double y) : x(x), y(y) {}

    bool operator < (const Point &oth) const {
        return x < oth.x;
    }
};

const int NMAX = 1e5;
int n;
Point points[NMAX];

double dist(int i, int j) {
    return sqrt((points[i].x - points[j].x) * (points[i].x - points[j].x) + (points[i].y - points[j].y) * (points[i].y - points[j].y));
}

mt19937 gen(clock());

int main() {
    ios_base :: sync_with_stdio(false);

    double alpha = 2 * (gen() % 1000) * 1e-3 * PI;
    double cs = cos(alpha), sn = sin(alpha);

    fin >> n;
    for(int i = 0; i < n; i++) {
        int x, y;
        fin >> x >> y;

        points[i] = Point(x * cs - y * sn, y * cs + x * sn);
    }

    sort(points, points + n);

    double minDist = INF;
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n && points[j].x - points[i].x < minDist; j++) {
            minDist = min(minDist, dist(i, j));
        }
    }

    fout << fixed << setprecision(6) << minDist;

    fin.close();
    fout.close();
    return 0;
}