Cod sursa(job #2710753)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 22 februarie 2021 23:10:09
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.07 kb
#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> pi;
typedef long double ld;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd(int l, int r)
{
	return uniform_int_distribution<int>(l, r)(rng);
}
 
ld between(pi a, pi b)
{
	return sqrt(1ll*(a.first-b.first)*(a.first-b.first) + 1ll*(a.second-b.second)*(a.second-b.second));
}
 
ld dist = 0;
ld truemin = 0;
 
int toInt(ld x)
{
	int y = x;
	return max(y, 1);
}
 
int hash2(pi p, int addx = 0, int addy = 0)
{
	p.first /= toInt(dist);
	p.second /= toInt(dist);
	p.first += addx;
	p.second += addy;
	return p.first^p.second;
}
 
vector<int> fastSolver(vector<pi> r)
{
	int n = r.size();
	vector<pi> v;
	vector<int> ans;
	unordered_map<int, vector<pi>> mp;
	for (int i = 0; i < n; ++i) {
		pi now = r[i];
		v.push_back(now);
		if (i == 0)
			continue;
		if (i == 1) {
			dist = between(v[0], v[1]);
			truemin = between(v[0], v[1]);
			ans.push_back(truemin);
			mp[hash2(v[0])].push_back(v[0]);
			mp[hash2(v[1])].push_back(v[1]);
			continue;
		}
		ld newmin = dist;
		for (int a = -1; a <= 1; ++a)
			for (int b = -1; b <= 1; ++b)
				for (auto point : mp[hash2(now, a, b)])
					newmin = min(newmin, between(now, point));
		mp[hash2(now)].push_back(now);
		truemin = min(truemin, newmin);
		ans.push_back(truemin);
		if (truemin*2 < dist) {
			dist = truemin;
			mp.clear();
			for (auto x : v)
				mp[hash2(x)].push_back(x);
		
		}
	}
	return ans;
}
 
vector<int> slowSolver(vector<pi> r)
{
	int n = r.size();
	truemin = between(r[0], r[1]);
	vector<int> ans;
	ans.push_back(truemin);
	for (int i = 2; i < n; ++i) {
		for (int j = 0; j < i; ++j)
			truemin = min(truemin, between(r[i], r[j]));
		ans.push_back(truemin);
	}
	return ans;
}
 
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

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

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

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

int main()
{
	InParser fin ("cmap.in");
	ofstream fout ("cmap.out");
	int n;
	fin >> n;
	vector<pi> v(n);
	for (int i = 0; i < n; ++i)
		fin >> v[i].first >> v[i].second;
	fastSolver(v);
	fout << fixed << setprecision(8) << truemin << "\n";
	return 0;
}