Pagini recente » Cod sursa (job #1984151) | Cod sursa (job #2043858) | Cod sursa (job #3160256) | Cod sursa (job #260642) | Cod sursa (job #2710755)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef 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*3 < 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;
}