Cod sursa(job #3342239)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 23 februarie 2026 14:37:24
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.13 kb
//https://www.infoarena.ro/problema/cmap

#ifdef _MSC_VER
	#define _CRT_SECURE_NO_WARNINGS
#elif  __GNUC__
	#pragma GCC optimize("Ofast,unroll-loops,inline")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

//#define _USE_MATH_DEFINES

#include <iostream>
//#include <fstream>
#include <utility>
#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <vector>
//#include <array>
//#include <list>
//#include <forward_list>
//#include <string>
//#include <cstring>
#include <cmath>
//#include <bitset>
//#include <queue>
//#include <stack>
//#include <map>
//#include <set>
//#include <unordered_map>
//#include <unordered_set>
#include <limits>
//#include <climits>
//#include <iomanip>
//#include <tuple>
//#include <numeric>
//#include <chrono>
//#include <memory>

using namespace std;

using int64 = int64_t;
using uint64 = uint64_t;
using int16 = int16_t;
using uint16 = uint16_t;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define all(x) (x).begin(), (x).end()
#define allg(x) (x).begin(), (x).end(), greater<int>()
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define rfor(i, st, dr) for(auto i=(st); i<=(dr); ++i)
#define for0(i,n) for(auto i=0; i<(n); ++i)
#define rfor0(i,n) for(auto i=(n)-1; i>=0; --i)
#define for1(i,n) for(auto i=1; i<=(n); ++i)
#define rfor1(i,n) for(auto i=(n); i>=1; --i)
#define foreach(x,a) for(auto& x : a)
#define cforeach(x,a) for(const auto& x : a)
#define ft first
#define sd second
#define cendl cout << "\n"
#define fendl fout << "\n"
#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

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

FILE* fin = fopen("cmap.in", "r");
FILE* fout = fopen("cmap.out", "w");

const int NRMAX = 100000;

struct Punct
{
	int x, y;

	bool operator<(const Punct& other) const
	{
		if (this->x == other.x)
			return this->y < other.y;
		return this->x < other.x;
	}

};

Punct p[NRMAX + 1], py[NRMAX + 1];
int n;


int64 dist(const Punct& a, const Punct& b)
{
	return (int64)(a.x - b.x) * (a.x - b.x) + (int64)(a.y - b.y) * (a.y - b.y);
}

int64 rezolvare(int st, int dr)
{
	if (dr - st <= 3)
	{
		int64 mini = numeric_limits<int64>::max();
		for (int i = st; i <= dr; ++i)
			for (int j = i + 1; j <= dr; ++j)
				mini = min(mini, dist(p[i], p[j]));
		return mini;
	}

	int mij = (st + dr) / 2;
	int64 d1 = rezolvare(st, mij);
	int64 d2 = rezolvare(mij + 1, dr);
	int64 d = min(d1, d2);

	vector<Punct> v;
	rfor(i, st, dr)
		if (abs(py[i].x - p[mij].x) <= d)
			v.pb(py[i]);

	for0(i, sz(v))
		for (int j = i + 1; j < sz(v) && (v[j].y - v[i].y) * (v[j].y - v[i].y) < d; ++j)
			d = min(d, dist(v[i], v[j]));


	return d;
}


int main()
{
	//FASTIO;

	fscanf(fin, "%d", &n);
	for1(i, n)
		fscanf(fin, "%d %d", &p[i].x, &p[i].y), py[i].x = p[i].x, py[i].y = p[i].y;

	sort(p + 1, p + n + 1);
	sort(py + 1, py + n + 1, [](const Punct& a, const Punct& b) { return a.y < b.y; });

	/*for1(i, n)
		cout << p[i].x << " " << p[i].y << "\n";*/

	fprintf(fout, "%.6lf\n", sqrt(rezolvare(1, n)));

	return 0;
}