Pagini recente » Cod sursa (job #1815211) | Cod sursa (job #819965) | Cod sursa (job #770363) | Cod sursa (job #1278710) | Cod sursa (job #1593275)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
const int MAXN = 100005;
const long long INF = 1ll << 62;
ifstream in("cmap.in");
ofstream out("cmap.out");
struct punct
{
long long x,y;
};
int n;
punct pct1[MAXN];
punct pct2[MAXN];
bool ordine_dupa_x(punct a, punct b)
{
if (a.x < b.x)
return true;
if (a.x > b.x)
return false;
return a.y < b.y;
}
bool ordine_dupa_y(punct a, punct b)
{
if (a.y < b.y)
return true;
if (a.y > b.y)
return false;
return a.x < b.x;
}
long long dist_lp(punct a, punct b)//distanta la patrat
{
long long dx = a.x - b.x;
long long dy = a.y - b.y;
return dx * dx + dy * dy;
}
punct pctaux[MAXN];
long long distminim(int st, int dr)
{
if (dr - st <= 1)
return INF;
if (dr - st == 1)
return dist_lp(pct1[st], pct2[dr]);//cazul banal
long long mij = (st + dr) / 2;
long long rasp = min(distminim(st, mij), distminim(mij + 1, dr));
sort(pct2 + st + 1, pct2 + dr + 1, ordine_dupa_y);
int l_pctaux = 0;
for (int i = st;i <= dr;++i)
if (pct2[i].x - pct1[mij].x <= rasp)
pctaux[++l_pctaux] = pct2[i];
for (int i = 1;i <= l_pctaux;++i)
for (int j = i + 1;j <= l_pctaux && j - i < 8;++j)
rasp = min(rasp, dist_lp(pctaux[i], pctaux[j]));
return rasp;
}
void citire()
{
in >> n;
for (int i = 1;i <= n;++i)
in >> pct1[i].x >> pct1[i].y;
}
int main()
{
citire();
sort(pct1 + 1, pct1 + n + 1,ordine_dupa_x);
for (int i = 1;i <= n;++i)
pct2[i] = pct1[i];
out << fixed << setprecision(6) << sqrt(distminim(1,n));
return 0;
}