Pagini recente » Cod sursa (job #2922808) | Cod sursa (job #2115247) | Rating florin (saulul) | Cod sursa (job #2415618) | Cod sursa (job #1593325)
#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];
inline long long minl(long long a, long long b)
{
return (a < b)?a:b;
}
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;
}
inline void interschimba(punct v[], int i, int j)
{
punct aux = v[i];
v[i] = v[j];
v[j] = aux;
}
punct pctaux[MAXN];
long long distminim(int st, int dr)
{
if (dr - st < 1)
return INF;
if (dr - st == 1)
{
if (!ordine_dupa_y(pct2[st], pct2[dr]))
interschimba(pct2, st, dr);
return dist_lp(pct1[st], pct1[dr]);//cazul banal
}
long long mij = (st + dr) / 2;
long long x1 = distminim(st, mij);
long long x2 = distminim(mij + 1, dr);
long long rasp = minl(x1, x2);
//sort(pct2 + st + 1, pct2 + dr + 1, ordine_dupa_y);
merge(pct2 + st, pct2 + mij + 1, pct2 + mij + 1, pct2 + dr + 1,pctaux + 1,ordine_dupa_y);
int j = 0;
for (int i = st;i <= dr;++i)
{
++j;
pct2[i] = pctaux[j];
}
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 = minl(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;
}