Cod sursa(job #2938327)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 11 noiembrie 2022 23:04:47
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
#define x first
#define y second

#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using Point = pair<double, double>;

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

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

int N;
double alpha, sn, cs;
Point pts[NMAX + 1];

Point rotate(const Point &a) {
	return {cs * a.x + sn * a.y, -sn * a.x + cs * a.y};
}

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

mt19937 gen(clock());

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

	fin >> N;

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

	for(int i = 1; i <= N; i++) {
		int x, y;
		fin >> x >> y;

		pts[i] = {x, y};
		rotate(pts[i]);
	}

	sort(pts + 1, pts + N + 1);

	double minDist = INF;

	for(int i = 1; i < N; i++) {
		for(int j = i + 1; j <= N && pts[j].x - pts[i].x <= minDist; j++) {
			minDist = min(minDist, Dist(pts[j], pts[i]));
		}
	}

	fout << fixed << setprecision(6) << minDist << '\n';
	return 0;
}