Cod sursa(job #3037760)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 26 martie 2023 13:22:40
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 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 == 262144) {
			sp = 0;
			fread(buff, 1, 262144, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[262144]();
		sp = 262143;
	}
	
	void close() {
		fclose(fin);
	}

	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, 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] = Point(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;
}