Pagini recente » Cod sursa (job #1050204) | Cod sursa (job #2844829) | Cod sursa (job #537741) | Cod sursa (job #2287545) | Cod sursa (job #2064831)
#include <iostream>
#include <fstream>
#include <math.h>
#include <stdlib.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define NMAX 100000
struct Punct{
int x, y;
};
int sortx(Punct &A, Punct &B)
{
return (A.x < B.x || (A.x == B. x && A.y < B.y));
}
int sorty(Punct &A, Punct &B)
{
return A.y < B.y;
}
double sq_dist(const Punct &A, const Punct &B)
{
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
Punct P1, P2;
double cmap(int p, int u, vector<Punct> &px, vector<Punct>&py)
{
if(p >= u)return NMAX;
if(u - p == 1)
{
if(py[p].y > py[u].y)
swap(py[p], py[u]);
P1 = py[p];
P2 = py[u];
return sq_dist(py[p], py[u]);
}
int m = (p + u) / 2;
double dmin_stg = cmap(p, m, px, py);
double dmin_dr = cmap(m + 1, u, px, py);
double dmin = min(dmin_stg, dmin_dr);
vector<Punct> t(u - p + 1);
merge(py.begin() + p, py.begin() + m + 1, py.begin() + m + 1, py.begin() + u + 1, t.begin(), sorty);
copy(t.begin(), t.end(), py.begin() + p);
int i, j;
vector<Punct> w;
for(i = p; i <= u; i++)
if(fabs(px[m].x - py[i].x) <= dmin)
w.push_back(py[i]);
for(i = 0; i < w.size(); i++)
{
for(j = i + 1; j < w.size() && j < i + 8; j++)
{
if(sq_dist(w[i], w[j]) < dmin)
{
dmin = sq_dist(w[i], w[j]);
P1= w[i];
P2 = w[j];
}
}
}
return dmin;
}
int main()
{
int n;
fin >> n;
vector<Punct> px(n), py(n);
int i;
for(i = 0; i < n; i++)
{
fin >> px[i].x >> px[i].y;
py[i].x = px[i].x;
py[i].y = px[i].y;
}
sort(px.begin(), px.end(), sortx);
float dmin = cmap(0, n - 1, px, py);
fout << fixed << setprecision(6) << sqrt(dmin) << '\n';
//fout << P1.x << " " << P1.y << '\n' << P2.x << " " << P2.y;
return 0;
}