Pagini recente » Cod sursa (job #302022) | Cod sursa (job #1184914) | Cod sursa (job #2307345) | Cod sursa (job #259769) | Cod sursa (job #2558082)
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Punct
{
int x, y;
bool operator < (const Punct& other) const
{
if (y == other.y)
return x < other.x;
return y < other.y;
}
};
int n;
Punct A[100001];
map<Punct, vector<int>> M;
bool Divide(int l, bool jos, bool dr) // jos, dr - offset de L / 2 la impartire? Returneaza true daca exista 2 puncte in acelasi patrat
{
bool gasit = false;
M.clear();
for (int i = 1; i <= n; ++i)
{
int x = A[i].x, y = A[i].y;
if (jos) x += l / 2;
if (dr) y += l / 2;
x /= l, y /= l;
M[{x, y}].push_back(i);
if (M[{x, y}].size() >= 2)
gasit = true;
}
return gasit;
}
int Cb() // Returneaza cea mai mica latura l pentru care la impartirea in patrate de l sa existe cel putin doua puncte in acelasi patrat
{
int st = 1, dr = 2000000001;
while (st <= dr)
{
int mij = st / 2 + dr / 2;
if (st % 2 == 1 && dr % 2 == 1)
++mij;
bool gasit = false;
for (bool jos : {false, true})
{
for (bool drp : {false, true})
{
if (Divide(mij, jos, drp))
{
dr = mij - 1;
gasit = true;
break;
}
}
if (gasit)
break;
}
if (!gasit)
st = mij + 1;
}
return st;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
{
int x, y;
fin >> x >> y;
A[i] = {x + 1000000000, y + 1000000000};
}
int l = Cb();
Divide(l, false, false);
double dmin = 3000000000.0d;
for (const pair<Punct, vector<int>>& patrat : M)
{
const Punct& p = patrat.first;
const vector<int>& El = patrat.second;
for (int dx = 0; dx <= 2; ++dx)
{
for (int dy = 0; dy <= 2; ++dy)
{
Punct p2 = {p.x + dx, p.y + dy}; // pozitia patratului vecin
if (M.find(p2) != M.end())
{
for (int el1 : El)
{
for (int el2 : M[p2])
{
if (el1 != el2)
{
long long c1 = (A[el1].x - A[el2].x) * (A[el1].x - A[el2].x);
long long c2 = (A[el1].y - A[el2].y) * (A[el1].y - A[el2].y);
dmin = min(dmin, sqrt(1.0d * c1 + 1.0d * c2));
}
}
}
}
}
}
}
fout << fixed << setprecision(10) << dmin;
return 0;
}