Cod sursa(job #2938338)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 11 noiembrie 2022 23:18:06
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 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>;

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 65536) {
			sp = 0;
			fread(buff, 1, 65536, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[65536]();
		sp = 65535;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

InParser 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;
}