Cod sursa(job #2938349)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 11 noiembrie 2022 23:26:16
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 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, cs, sn;
Point pts[NMAX + 1];

double Dist(const int &a, const int &b) {
	return sqrt((pts[a].x - pts[b].x) * (pts[a].x - pts[b].x) + (pts[a].y - pts[b].y) * (pts[a].y - pts[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] = {cs * x + sn * y, -sn * x + cs * y};
	}

	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(i, j));
		}
	}

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

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